• Nechť L je
RJ. Pak existuje k ³ 1 takové,
že:
pokud z Î L a
|z| ³ k, pak existuje u,v,w: z = uvw,
1) v
¹ e 2) |uv|
£ k 3)
pro každé m ³ 0, uvmw Î L
Pumping lemma pro RJ
Příklad: pro RV r = ab*c, L(r) je regulární.
• pro z = abc: z Î L(r)
a |z|
³ 3:
u v w
uv0w
= ab0c = ac Î L(r)
uv1w
= ab1c = abc Î L(r)
uv2w
= ab2c = abbc Î L(r)
...
v ¹ e, |uv| = 2 £ 3
• pro z = abbc: z Î L(r) a |z| ³ 3:
u v w
uv0w
= abb0c = abc Î L(r)
uv1w
= abb1c = abbc Î L(r)
uv2w
= abb2c = abbbc Î L(r)
...
...
v ¹ e, |uv| = 2 £ 3
Myšlenka: Pumping lemma ukazuje nekonečné iterace některých podřetězců v řetězcích v
RJ.
Pro tento jazyk existuje k = 3 takové, že 1), 2) a 3) platí.
2/26