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.