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