Pumping lemma: Příklad 1/2
Dokažme,
že L = {anbncn : n ³ 1} není BKJ.
1) Předpokládejme, že L je
BKJ. Nechť k ³ 1 je konstanta z pumping lemmy pro daný jazyk L.
2) Nechť z = akbkck: akbkck Î L, |z| = |akbkck| = 3k ³ k
3) Všechny
dekompozice z na uvwxy; vx ¹ ε, |vwx| £ k:
aaaaa…aabb…bb…bbcc…ccccc
k k k
a) vwx Î {a}*{b}*,
vx ¹ e
b) vwx Î
{b}*{c}*,
vx ¹ e
16/31