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

Now, how can we define a machine to accept $\{ab,aabb\}$? Or $\{ab,aabb,aaabbb\}$? We need to add more states. See the animation below.

A machine with a finite number of states will never have enough states to match an arbitrarily large number of symbols.

The reasoning above satisfies our intuition, but it is not a proof! If $L_{ab}=a^nb^n$ were regular, then per the pumping theorem, we could pick any string in this language of at least $p$ symbols in length, and partition it into three concatenated substrings, $xyz$, and then pump $y$ however much we require and still obtain a string in the language. This is how infinite regular languages behave. We’ll choose the string $a^pb^p$, which is more than long enough for us to invoke the pumping theorem and show that it cannot be partitioned this way.

If $L_{ab}$ were regular, then, using the pumping theorem, we could partition $a^pb^p$ into three parts, $xyz$. Since the condition $|xy| \leq p$ must hold, we know that the substring $y$ ...