u
vwx
y
Pumping Lemma: Example 2/2
a) vwx Î {a}*{b}*:
• 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