Proof of Pumping Lemma 1/3
• Let L be a regular language. Then, there exists DFA  M = (Q, S, R, s, F), and L = L(M).
• For z Î L(M), M makes |z| moves and M visits
|z| + 1 states:
 sa1a2…an |– q1a2…an |– … |– qn-1an |– qn
|z|
|z| + 1 states
q1
s
qn
a1
a2
…
qn-1
an
• for z = a1a2 ...an:
an-1
4/26