Pumping Lemma: Application II. 1/3
• We can use the pumping lemma to prove
   some other theorems.
Illustration:
• Let M be a DFA and k be the pumping lemma constant (k is the number of states in M). Then,
L(M) is infinite Û there exists z Î L(M), k £ |z| < 2k
Proof:
1) there exists z Î L(M), k £ |z| < 2k Þ L(M) is infinite:
if z Î L(M), k £ |z|, then by PL:
z = uvw, v ¹ e, and for each m ³ 0: uvmw Î L(M)
L(M) is infinite
10/26