Pumping Lemma: Příklad
Dokažme,
že L
= {anbn : n ³ 0} není regulární:
1) Předpokládejme, že L je
regulární. Nechť k
³ 1 je konstanta
z pumping lemmy pro jazyk L.
2) Nechť z = akbk: akbk Î L, |z| = |akbk| = 2k ³ k
3) Všechny
dekompozice z na uvw, v
¹ e, |uv| £ k:
8/26
u
v
w
a a…a abb…bb
k k
|uv| £ k
• pumping lemma: uv0w
Î L
k - i <
k
a abb…bb Ï L
u
w
• uv0w = uw =
Spor!
4) Proto L není regulární
jazyk