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.