= Solution
The <pumping lemma for regular languages> states that for every <regular language> $L$ there is an integer $N$ such that every $w\in L$ with $|w|\geq N$ can be written
$$
w=xyz
$$
with
$$
|xy|\leq N,\qquad |y|\geq1,\qquad
xy^rz\in L\quad\text{for every }r\geq0.
$$
To prove it, let a <deterministic finite automaton> with $N$ states recognize $L$. During the reading of the first $N$ symbols of an accepted word $w$, the automaton visits $N+1$ states, including the initial state. By the <pigeonhole principle>, two of them agree, say $q_i=q_j$ with $0\leq i<j\leq N$. Let $x$ be the first $i$ symbols, $y$ the next $j-i$ symbols, and $z$ the remaining suffix. Reading $y$ is a nonempty closed path from $q_i$ to itself. Traversing this path any number $r\geq0$ of times and then reading $z$ therefore reaches the same accept state. This proves all three assertions.
Back to article page
