Pumping Lemma: Aplikace II. 3/3
Pokud z0 Î L(M) a |z0| ³ k, PL zaručuje: z0 = uvw, |uv| £ k a pro každé m ³ 0, uvmw Î L(M)
b) Dokážeme sporem:
SPOR!
Předpokl., že existuje z
Î L(M), |z|
³ k
k
2k
pro m = 0: uvmw = uw Î L(M)
Celkově: uw Î L(M), |uw| ³ k a |uw| <
|z0|!
z0 není nejkratší řetězec splňující z0 Î L(M), |z0| ³ k
³ 2k
£ k
Nechť z0 je nejkratší
řetězec splňující z0 Î L(M), |z0| ³ k
Protože neexistuje z Î L(M), k
£ |z| < 2k, musí: |z0| ³ 2k
a neexistuje
z Î L(M), k £ |z|
< 2k
existuje z Î L(M), k £ |z|
< 2k
• existuje z Î L(M), |z|
³ k
Þ
12/26