```Pumping Lemma

Let M have n states, {k0, k1, ..., k_n-1},
Let w = a1 a2 ... am m = |w| >= n

As M reads w, states visited are q0=k0, q1, q2, ..., qm

Because there exists only n states two of {q0, ..., qm} are the same
(by the pigeonhole principle).

+-------+ a1 ... aj     +-------+ a_k+1 ... am  +--+
|k0 = q0+/\/\/\/\/\/\/\>|qj = qk|/\/\/\/\/\/\/\>|qm|
+-------+               +-------+               +--+
|       ^
|       |
+-------+
a_j+1 ... ak

Thus the string goes around a cycle in M and we could delete
a_j+1 ... ak or duplicate a_j+1 ... ak and end up in the same state km

i.e., delta(k0, a1 ... aj ak+1 ... am = delta(k0, a1 ... am) = qm
and   delta(k0, a1 ... aj (aj+1 ... ak)^i ak+1 ... am)
= delta(s0, a1 ... am) = qm for all i

--------------------------------------------------------------------------------

Let L be regular.  Then there xists n such that
for all x in L with |x| >= n there exists u, v, w in Sigma* s.t.

1.  x = uvw
2.  |uv| <= n
3.  |v| >= 1
4.  forall i>=0, uv^iw in L

--------------------------------------------------------------------------------

Proof.  L regular => there xists DFA M for L.

Let n = #states(M).  By the previous argument, delta(q0, w) in F
with |x| >= n => within first n characters of x there is a segment
of length >= 1 that can be omitted or replicated any number of times
and still lead to the same state of F.

Example

L = {0^i 1^i:  i>=0} is not regular.

Proof.  Suppose L is regular, and obtain contradiction.

L regular => by PL that there exists n with properties above.
Let x = 0^n 1^n in L and |x| >= n.
By PL, there exist u, v, w s.t.

1.  x = uvw
2.  uv is a prefix of 0^n
3.  v in 0+
4.  forall i uv^iw in L

Thus u = 0^s, v = 0^t, w = 0^p1^n

Where s+t+p = n
s+t <= n.
t >= 1

Property 4 is violated, because if i = 0, we obtain
uv^0w = 0^{n-t}1^n, which is not in L because t >= 1.
```