Search code examples
regular-language

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?

Solution

  • 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.