
u
vwx
y
Pumping lemma: Příklad 2/2
• 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