Showing that a language is not regular (4.2)

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

$$L = \{ 0^n1^n \mid n\in \mathbb{N}\}$$

i.e. the language of workds which start with a number of 0s followed by the same number of $1$s. Note that this is different to $L(0^*1^*)$ which is the language of words of sequences of 0s followed by a sequence of $1$s but the umber has not to be identical (and which we know to be regular because it is given by a regular expression).

Why can $L$ not be recognized by a computer with finite memory? Assume we have 32 Megabytes of memory, that is we have $32*1024*1024*8 = 268435456$ bits. Such a computer corresponds to an enormous DFA with $2^{268435456}$ states (imagine you have to draw the transition diagram). However, the computer can only count until $2^{268435456}$ 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 $n$.

We shall now show a general theorem called the pumping lemma which allows us to prove that a certain language is not regular.