The pumping lemma

Theorem 4.1   Given a regular language $L$, then there is a number $n\in\mathbb{N}$ such that all words $w\in L$ which are longer than $n$ ($\vert w\vert\geq n$) can be split into three words $w=xyz$ s.t.

1. $y\not=\epsilon$

2. $\vert xy\vert\leq n$

3. for all $k\in\mathbb{N}$ we have $xy^kz\in L$.

Proof: For a regular language $L$ there exists a DFA $A$ s.t. $L=L(A)$. Let us assume that $A$ has got $n$ states. Now if $A$ accepts a word $w$ with $\vert w\vert\geq n$ it must have visited a state $q$ twice:

We choose $q$ s.t. it is the first cycle, hence $\vert xy\vert\leq n$. We also know that $y$ is non empty (otherwise there is no cycle).

Now, consider what happens if we feed a word of the form $xy^iz$ to the automaton, i.e. s instead of $y$ it contains an arbotrary number of repetetions of $y$, including the case $i=0$, i.e. $y$ is just left out. The automaton has to accept all such words and hence $xy^iz \in L$

$\Box$