1
$\begingroup$

I'm struggling in understanding how to recognize irregular languages. I know what the meaning of irregular language but still find it hard to recognize. Are there any tips to recognize better and to know which is regular and which not?

For example, which of the following is not regular, and what gives you the intuition? \begin{align} L_1 &= \{a^ib^i \mid i \ge 0 \} \\ L_2 &= \{a^ib^j \mid i,j \ge 0\} \\ L_3 &= \{a^nb^nc^md^m \mid n,m \ge 1 \} \end{align}

$\endgroup$
0
$\begingroup$

The language $L_1$ is the quintessential example of a non-regular language. Intuitively, finite automata cannot count, so they cannot ascertain that the number of $a$'s is the same as the number of $b$'s. Alternatively, an automaton must "remember" how many $a$'s it has seen, which is impossible since there are infinitely many possible number of $a$'s. This intuition can be formalized using Myhill–Nerode theory: if $q_n$ is the state that a DFA for $L_1$ is at after reading $a^n$, then $q_n \neq q_m$ for $n \neq m$, since $a^nb^n \in L_1$ while $a^mb^n \notin L_1$; so there must be infinitely many states.

The language $L_2$ corresponds to the regular expression $a^*b^*$, so is regular.

The language $L_3$ is a "generalization" of $L_1$ (this can be made precise: $L_1$ is a quotient of $L_3$, $L_1 = L_3/\{cd\}$). Once again, an automaton needs to count how many $a$'s there are, which is impossible.

$\endgroup$
1
  • $\begingroup$ thank you ! helped a lot $\endgroup$ – user1 Feb 1 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.