• 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