• Nechť L je BKJ. Potom existuje k ³ 1 takové, že: pokud z Î L a |z| ³ k, pak existuje u, v, w, x, y tak, že z = uvwxy, přičemž dále platí:
1) vx ¹ ε 2) |vwx| £ k 3) pro každé m ³ 0: uvmwxmy Î L
Pumping lemma pro BKJ
Příklad:
G = ({S, A}, {a, b, c}, {S ® aAa, A ® bAb, A ® c}, S) generuje L(G) = {abncbna : n ³ 0}, tedy L(G) je BKJ.
Existuje k = 5 takové, že 1), 2) and 3) platí:
• pro z = abcba: z Î L(G) a |z| ³ 5:
u v w x y
uv0wx0y = ab0cb0a = aca Î L(G)
uv1wx1y = ab1cb1a = abcba Î L(G)
uv2wx2y = ab2cb2a = abbcbba Î L(G)
Textové pole: ...
...
|vwx| = 3: 1 £ 3 £ 5
vx = bb ¹ ε
Textové pole: ...
...
• pro z = abbcbba: z Î L(G) a |z| ³ 5:
13/31