9. Example of nonregular language

Example of nonregular language

Consider the following language over the alphabet $\{a,b\}$:

$$\begin{array}{rl}L& =\text{all words starting with a word of }a\text{’s followed}\\ & \text{by an equal-length word of }b\text{’s}\\ & =\{a^n{b}^n|n=0,1,2,...\}\end{array}$$

Suppose that a finite automaton $A$ tries to recongise words in this language. Then $A$ must store the entire sequence of $a$‘s before the first $b$ shows up. Otherwise $A$ will not be able to compare the length of the coming word of $b$s with the length of the prefix of $a$s.

As each automaton is capable for a fixed finite amount of storage with the help of its states, no automaton $A$ exists such that $L(A)=L$.

There is a precise mathematical proof justifying this informal argument: this language $L$ is indeed not regular.