CODEWITHSUNDEEP
regular-language
hkoosha
hkoosha

Reputation: 1146

Isn't every language regular, according to formal definition of it?

This is the definition of regular languages from Wikipedia's article:

The collection of regular languages over an alphabet Σ is defined recursively as follows:

  • The empty language Ø is a regular language.

  • For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.

  • If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.

  • No other languages over Σ are regular.

Now think about aⁿbⁿ which we know is not regular, but doesn't it pass the above rules?

{a} is regular, so is {b} and also their concatenation and thus the mentioned lang!

it feels like I'm mistaking set of languages which is, in other words, set of sets; for set of words which is, the language?

Upvotes: 2

Views: 259

Answers (3)

Ami Tavory
Ami Tavory

Reputation: 76297

You are mistaken in your statement that you can form this specific language from the rules. Formally, this follows from the Pumping Lemma. To address the reasoning in your question, though:

  • {a} is regular, so by repeated concatenation, {a^m} is regular

  • {b} is regular, so by repeated concatenation, {b^n} is regular

so their concatenation, which is anything of the form {a^m b^n} is regular as well, but it is precisely the constraint m == n that you cannot formulate via this family.

Upvotes: 1

Alexander Weinert
Alexander Weinert

Reputation: 665

You're right, {a} is regular and {b} is regular. Thus, by the rules you mentioned, their concatenation is regular as well. However, the concatenation of two languages is defined as {vw | v in L_1, w in L_2}. Since both L_1 and L_2 only contain a single word (a and b, respectively), this definition is equivalent to {vw | v = a, w = b}, which is the set {ab}.

Thus, the concatenation of the two languages is the set {ab}, not a^n b^n.

Upvotes: -1

orlp
orlp

Reputation: 117681

aⁿbⁿ is a language that contains only the strings with nx as followed by nxbs.

You can create a regular language that is a superset of this language, but not this language itself.

Upvotes: 1

Related Questions