The above two problems demonstrate the usefulness of elementary combinatorics to prove results regarding regularity. Using these basic ideas, we can construct very powerful results in automata theory. One of the most fundamental is stated below.
Theorem 4.1 (Pumping Lemma). Let L be a regular language. Then there exists an integer P \geq 1 such that any w \in L with |w| \geq P can be written as w = xyz with y not equal to the empty string such that
- |xy| \leq P, and
- for all integers i \geq 0, the string xy^i z is also in L.
We call P the pumping length of L.
In this problem, we give a proof of the lemma and then see how it can be used to solve some regularity problems.
(a) Suppose M is a DFA which decides L. Let p be the number of states of M. Consider an input
Let q_{k} be the state the automaton is in after reading the character s_{k}. Show that there exist integers 0 \leq i < j \leq p such that q_{i} = q_{j}.
(b) Let i and j be as above. Define
Show that these x, y, and z fit the description given in the Pumping Lemma, where P = p.
(c) Using the Pumping Lemma, show that the language
is not regular.