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 1 Lemma o vkládání pro regulární jazyky 1.1 Důkaz 1.2 Konečnost regulárních jazyků 2 Lemma o vkládání pro bezkontextové jazyky 3 Použití

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

[editovat] 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ý.

Můžeme 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 i 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, nemohli jsme 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, náš původní předpoklad, že L je bezkontextový, je nepravdivý.  Q.E.D.