
u
vwx
y
Pumping Lemma: Example
2/2
• uv0wx0y = uwy =
All these decompositions lead to a
contradiction!
4) Therefore, L is not a CFL.
a a…aabb …b bcc …cc
k k k
• Pumping lemma:
uv0wx0y Î L

u
w
y
a a …aabb…b bcc …cc Ï L
Note: uwy contains k cs, but fewer than k as or bs.


u
vwx
y
b) vwx Î {b}*{c}*:
• uv0wx0y = uwy =
aa…aab b …bbcc …c c
k k k


y
w
u
aa …aab b …bbcc …c c
Ï
L
Note: uwy contains k as, but fewer than k bs or cs.
• Pumping lemma:
uv0wx0y Î L
17/31