Lemma o vkládání

V teorii formálních jazyků je lemma o vkládání (pumping lemma) výrok, že každý formální 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í.

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 xyⁱz patří do L pro každé i≥0.

Důkaz

Lemma o vkládání lze poměrně snadno dokázat přímo: je-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 průchod v automatu je po nějaké smyčce – tu je možné buď zcela vypustit ($i=0$) nebo po ní naopak projít vícekrát ($|xy|\leq p$, neboť pokud bylo ještě před dokončením smyčky navštíveno více stavů než je celkový počet stavů, již dříve muselo při průchodu dojít ke smyčce a je možné 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 vpustit do stavu q3 (ad), nebo naopak po smyčce projít libovolněkrát (abcbcbcbcd).

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, $n\leq |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 není žádné takové slovo nalezeno, 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 je odstraněním smyčky nalezeno slovo dlouhé alespoň $|u|=n$, které by však bylo zachyceno již dříve.

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 uvⁱxyⁱz patří do L pro každé i ≥ 0.

Použití

Lemma o vkládání pro bezkontextové jazyky může být použito k dokázání toho, že určitý jazyk NENÍ bezkontextový.

Lze ukázat, že jazyk L = {a^jb^jc^j, j≥0} NENÍ bezkontextový.

1. Předpokládejme, že L je bezkontextový
   1. Podmínky:
      1. | vxy | ≤ p. To znamená, že prostřední část není příliš dlouhá.
      2. vy ≠ ε (prázdné). Protože v a y jsou pumpované úseky, tato podmínka říká, že alespoň jeden z řetězců, které pumpuje, musí být neprázdný.
      3. Pro všechna i ≥ 0, uvⁱxyⁱz náleží L. To znamená, že dva řetězce v a y mohou být “pumpovány” libovolný počet krát, včetně 0, a výsledný řetězec bude stále náležet jazyku L.
2. Jestliže w ∈ L kde | w | > p, pak z toho plyne, že w = uvxyz, kde | vxy | ≤ p
3. Nyní si zvolíme hodnotu pro j takovou, která je větší než p.
4. Pak, ať už se vxy v řetězci a^jb^jc^j nachází kdekoliv, vxy nemůže obsahovat více než dvě různá písmena, protože nejpravější a je j+1 pozic vzdáleno od nejlevějšího c.
   1. Př.: Může se stát, že jsou to všechna áčka, všechna béčka, nebo všechna céčka, nebo to mohou být áčka a béčka, nebo to mohou být béčka a céčka.
      1. Řetězec vxy tedy nemůže obsahovat více než dvě různá písmena, ale podle lemma o vkládání zase také nemůže být úplně prázdný, tedy musí obsahovat alespoň jedno písmeno.
5. Nyní můžeme začít „pumpovat“
   1. Protože uvxyz je v L, uv²xy²z musí být také v L. Protože v a y nemohou být obě současně prázdné, | uv²xy²z | > | uvxyz |, museli jsme přidat nějaká písmena.
   2. Ale protože vy neobsahuje všechny tři různá písmena, nebylo možné přidat stejný počet nových exemplářů od všech písmen. Napumpovali jsme tedy od některého písmena více a popřeli jsme tím původní definici L. Tedy, uv²xy²z nemůže náležet L.
      
6. Došli jsme ke sporu. Tedy, původní předpoklad, že L je bezkontextový, je nepravdivý.  Q.E.D.
   

Externí odkazy

• Obrázky, zvuky či videa k tématu Lemma o vkládání na Wikimedia Commons