Regular languages are languages which can be recognized by a computer with finite (i.e. fixed) memory. Such a computer corresponds to a DFA. However, there are many languages which cannot be recognized using only finite memory, a simple example is the language
Why can not be recognized by a computer with finite memory? Assume
we have 32 Megabytes of memory, that is we have
bits. Such a computer corresponds to an enormous DFA with
states (imagine you have to draw the transition
diagram). However, the computer can only count until
if
we feed it any more 0s in the beginning it will get confused!
Hence, you need a (potentially) infinite amount of memory to recognize
.
We shall now show a general theorem called the pumping lemma which allows us to prove that a certain language is not regular.