• Let L be CFL. Then, there exists k ³ 1 such that: if z Î L and |z| ³ k then there exist u, v, w, x, y so
z = uvwxy and
1) vx ¹ ε 2) |vwx| £ k 3) for each m ³ 0, uvmwxmy Î L
Pumping Lemma for CFL
Example:
G = ({S, A}, {a, b, c}, {S ® aAa, A ® bAb, A ® c}, S) generate L(G) = {abncbna : n ³ 0},  so L(G) is CFL.
There is k = 5 such that 1), 2) and 3) holds:
• for z = abcba: z Î L(G) and |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: ...
...
• for z = abbcbba: z Î L(G) and |z| ³ 5:
13/31