• 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)
...
|vwx| = 3:
1 £
3 £ 5
vx = bb ¹ ε
...
• pro z = abbcbba: z Î L(G)
a |z| ³ 5:
13/31