Nonregular Languages

Examples of nonregular languages

We’ll use the pumping theorem to prove that the following languages are not regular:

• The language $L_{ab}=a^nb^n$.
• The language of palindromes.
• The language of repeated halves, $\{ww \;|\; w \in (a+b)^*\}$.
• The language over $\Sigma=\{(,)\}$ of balanced parentheses.
• The language $\{a^mb^n \;|\; m > n\}$.
• The language PRIME = $\{a^n\}$, where $n$ is a prime number.
• The language $\{a^{n^2} \;|\; n>0\}$.

The language $L_{ab}$

We’ll now show that the language $L_{ab}=a^nb^n$ is not regular by showing that it does not satisfy the pumping theorem.

Intuitively, we can surmise that $L_{ab}$ is not regular because a finite machine has no way to track an arbitrarily large number of $a$'s to match the subsequent $b$'s. We can only go so far before we run out of states. Consider the diagram below accepting the singleton language $\{ab\}$. (Once again, we omit the jail state for readability.)