u
vwx
y
Pumping lemma: Příklad 2/2
a) vwx Î {a}*{b}*:
• uv0wx0y = uwy =
Všechny dekompozice vedou ke sporu!
4) Proto L není bezkontextový jazyk.
a a…aabb …b bcc …cc
k        k               k
• Pumping lemma:
      uv0wx0y Î L
u
w
y
a a …aabb…b bcc …cc Ï L
Pozn.: uwy obsahuje „k“ symbolů c, ale méně než „k“ symbolů a nebo b
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
Pozn.: uwy obsahuje „k“ symbolů a, ale méně než „k“ symbolů b nebo c
• Pumping lemma:
      uv0wx0y Î L
17/31