Pumping lemma: Aplikace II. 1/3
• Pumping lemmu je možné použít k dokazování dalších tvrzení.
Ilustrace:
• Nechť M je DKA a k konstanta z pumping lemmy (k je počet stavů v M). Potom platí:
L(M) je nekonečný Û existuje z Î L(M), k £ |z| < 2k
Důkaz:
1) existuje z Î L(M), k £ |z| < 2k Þ L(M) je nekonečný:
pokud z Î L(M), k £ |z|, potom podle PL:
z = uvw, v ¹ e a dále pro každé m ³ 0: uvmw Î L(M)
L(M) je nekonečný
10/26