Lemma o vkládání
Z Wikipedie, otevřené encyklopedie
V teorii formálních jazyků je lemma o vkládání (pumping lemma) výrok, že každý jazyk z dané třídy jazyků může být „napumpován“: každé dostatečně dlouhé slovo v daném jazyce může být rozděleno na části, jejichž zopakováním lze získat opět nějaké slovo z jazyka. To znamená, že pokud pro danou třídu jazyků existuje lemma o vkládání, každý jazyk v této třídě, který není konečný, bude obsahovat nekonečně mnoho slov vyprodukovatelných jednoduchým pravidlem daným tímto lemmatem (v případě konečných jazyků lze onu „dostatečnou délku slova“ nastavit na více, než je délka nejdelšího slova v jazyce).
Dvě nejdůležitější lemmata o vkládání jsou lemmata pro regulární jazyky a pro bezkontextové jazyky. Obě tato lemmata se využívají k důkazu skutečnosti, že jazyk neleží v dané třídě, nemohou být použity k důkazu toho, že jazyk v dané třídě leží. Lemma o vkládání je totiž podmínkou nutnou, nikoliv postačující.
Obsah |
[editovat] Lemma o vkládání pro regulární jazyky
Pokud je jazyk L regulární, existuje číslo p > 0 tak, že každé slovo w z L, pro které platí |w| ≥ p, lze zapsat ve tvaru w = xyz, kde pro slova x, y a z platí, že |xy| ≤ p, |y| > 0 a xyiz patří do L pro každé i≥0.
[editovat] Důkaz
Lemma o vkládání lze poměrně snadno dokázat přímo: stačí si uvědomit, že vezmeme-li p větší nebo rovno počtu stavů, při zpracování dostatečně dlouhého slova se již automat musí nutně do nějakého stavu dostat alespoň dvakrát, tedy jsme ovšem v automatu prošli po nějaké smyčce - tu můžeme buď zcela vypustit (i = 0) nebo po ní naopak projít vícekrát (
, neboť pokud jsme ještě před dokončením smyčky prošli více stavy, než je celkový počet stavů, již jsme nutně museli nějakou smyčkou projít dříve a můžeme pumpovat tu; | y | > 0, neboť smyčka není prázdná).
Pokud např. automatu znázorněnému na obrázku předložíme slovo abcd, automat projde stavem q1 dvakrát a přechody bc vytvořily smyčku. Tu můžeme zcela vypustit a stav q1 rovnou opustit do stavu q3 (ad), nebo naopak po smyčce projít libovolněkrát (abcbcbcbcd).
[editovat] Konečnost regulárních jazyků
Lemma o vkládání lze také využít k algoritmickému rozhodování, zda je daný regulární jazyk konečný: stačí projít všechna slova délky n až 2n (kde n je počet stavů). Pokud existuje nějaké takové slovo u, 
, dle lemmatu jej jistě lze pumpovat (i při omezení n na počet stavů – viz důkaz lemmatu) a tak vytvořit nekonečně mnoho dalších slov. Pokud žádné takové slovo nenajdeme, je jazyk jistě konečný. Stačí přitom prohledat jen prostor slov, pro která | u | < 2n: smyčka může mít délku nejvýše n (prochází-li všechny stavy), tedy pokud | u | = 2n, dle pumping lemmatu jsme odstraněním smyčky dostali slovo dlouhé alespoň | u | = n, které bychom však již zachytili dříve.
[editovat] Lemma o vkládání pro bezkontextové jazyky
Pokud je jazyk L bezkontextový, existuje číslo p > 0 tak, že každé slovo w z L, pro které platí |w| ≥ p, lze zapsat ve tvaru w = uvxyz, kde pro slova u, v, x, y a z platí, že |vxy| ≤ p, |vy| ≥ 1, a uvixyiz patří do L pro každé i ≥ 0.
