Pumping lemma: Aplikace I.
• Pomocí pumping lemmy pro RJ často provádíme důkaz sporem, že daný jazyk není regulární:
Předpokládejme, že L je
regulární
Uvažujme PL konstantu k a vyberme z Î L, jehož
délka je závislá na k tak, že
|z| ³ k je vždy
pravdivé
Pro všechny dekompozice
z na uvw, v
¹ e, |uv| £ k ukážeme:
existuje m ³ 0, pro
které uvmw Ï L;
ale podle PL platí vztah: uvmw Î L
SPOR
špatný předpoklad
Proto
L není regulární
7/26