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