Rekurzivní jazyk

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Formální jazyk L je rekurzivní, pokud existuje nějaký Turingův stroj (dále TS), který slova z tohoto jazyka pouze akceptuje anebo zamítá (nezacyklí se), tzn. vždy skončí po konečném počtu kroků. Pokud takový TS M existuje, říkáme, že TS M rozhoduje jazyk L. Rekurzivní jazyk je podmnožinou rekurzivně spočetného jazyka.

Uzávěrové vlastnosti[editovat | editovat zdroj]

Třída rekurzivních jazyků je uzavřená na sjednocení, průnik, zřetězení, iteraci, komplement (doplněk) a rozdíl. To znamená, že pokud jsou některé jazyky rekurzivní, jsou rekurzivní i jazyky vzniklé z nich za pomocí výše uvedených operací.

Důkaz uzavřenosti sjednocení[editovat | editovat zdroj]

Máme-li jazyky L1 a L2, které jsou rekurzivní, existují i TS M1 a M2, které tyto jazyky rozhodují. Sestrojíme-li sjednocení jazyků L1 a L2, vznikne nám nový jazyk Ls. Tento nový jazyk Ls bude rozhodován TS Ms, který bude pro slovo w postupovat takto:

  1. Simuluj TS M1 pro slovo w. Pokud TS M1 slovo přijme, přijmi slovo. Pokud odmítne, pokračuj dále.
  2. Simuluj TS M2 pro slovo w. Pokud TS M2 slovo přijme, přijmi slovo. Pokud odmítne, odmítni slovo w.

Vzhledem k tomu, že oba TS M1 i M2 rozhodují rekurzivní jazyk, nikdy se nezacyklí a vždy buď přijmou slovo nebo ho odmítnou. A protože jde o sjednocení, stačí, když alespoň jeden z původních TS slovo přijme.

Důkaz uzavřenosti průniku[editovat | editovat zdroj]

Máme-li jazyky L1 a L2, které jsou rekurzivní, existují i TS M1 a M2, které tyto jazyky rozhodují. Sestrojíme-li průnik jazyků L1 a L2, vznikne nám nový jazyk Lp. Tento nový jazyk Lp bude rozhodován TS Mp, který bude pro slovo w postupovat takto:

  1. Simuluj TS M1 pro slovo w. Pokud TS M1 slovo odmítne, odmítni slovo. Pokud přijme, pokračuj dále.
  2. Simuluj TS M2 pro slovo w. Pokud TS M2 slovo odmítne, odmítni slovo. Pokud přijme, přijmi slovo w.

Turingův stroj ověřuje platnost podobně jako v předchozím kroku, s tím rozdílem, že tentokrát musí slovo akceptovat oba TS, ne pouze jeden.

Důkaz uzavřenosti komplementu[editovat | editovat zdroj]

Nechť jazyk L je rekurzivní. Pak jistě existuje TS M, který tento jazyk rozhoduje. Tento TS M pracuje tak, že všechna slova w z L přijme a všechna slova z L' (= doplněk jazyka L) odmítne. Nový TS M', který bude rozhodovat jazyk L' sestrojíme takto:

  1. Simuluj činnost TS M pro vstup w.
  2. Pokud TS M slovo přijme, odmítni. Pokud TS M slovo odmítne, přijmi.

Nový TS M' bude jednoduše vracet přesně opačné výsledky, než původní TS M. Tento TS M' rozhoduje jazyk L'.

Důkaz uzavřenosti zřetězení[editovat | editovat zdroj]

Zřetězením dvou rekurzivních jazyků L1 a L2 vznikne nový jazyk Lz, který obsahuje slova vzniklá zřetězením (spojením) všech slov z L1 se všemi slovy z L2. Příklad: L1 = {ab, abc}, L2 = {cd, de}. Lz = {abcd, abde, abccd, abcde}. Nyní bychom potřebovali nějaký algoritmus, který by zjistil, zda dané slovo patří do Lz. Vstupní slovo musí být konečné, takže ho můžeme rozdělit na dvě části. Přitom pokud má slovo délku n, můžeme ho na dvě části rozdělit n+1 způsoby (předpokládáme, že jazyk může obsahovat epsilon ε – prázdné slovo). Například slovo web můžeme rozdělit čtyřmi způsoby na: ε+web, w+eb, we+b, web+ε. Pokud se budeme snažit zjistit, zda je slovo w obsaženo v Lz, stačí nám najít taková slova m, n, pro která platí m+n=w a zároveň m je z L1 a n z L2. TS Z, který bude rozhodovat, zda w patří do Lz, pak bude postupovat takto (TS M1 rozhoduje L1 a M2 rozhoduje L2):

  1. Vygeneruj množinu R všech možných rozkladů slova w. R = \left\{ [m, n] | m+n=w \wedge m\in L_1 \wedge n\in L_2\right\}.
  2. Prozkoumej všechny dvojice v R. Aktuálně procházenou dvojici označme D.
    1. Simuluj TS M1 pro Dm. Pokud M1 odmítá, jdi zkusit další dvojici.
    2. Simuluj TS M2 pro Dn. Pokud M2 odmítá, jdi zkusit další dvojici. Pokud přijímá, TS Z přijímá slovo w.
  3. TS Z odmítá slovo w.

Poznámka na konec: TS M1 i M2 rozhodují své jazyky, takže se nikdy nezacyklí.

Příklad Rekurzivního jazyka[editovat | editovat zdroj]

S rekurzivními jazyky se můžeme často setkat v běžném programování, kde obvykle řešíme problémy, které vyřešit lze. Takže například jazyk obsahující všechna slova, která začínají písmenem „a“. Obecně jakýkoliv regulární jazyk je zároveň rekurzivním jazykem, protože každý konečný automat můžeme simulovat na TS. Rekurzivním jazykem je i množina trojic [a, b, c], pro které platí a*b=c. Ukážeme si, jak by mohl pracovat TS M, který by prováděl pouze násobení přirozených čísel a*b. Předpokládáme, že používáme vícepáskový TS.

  1. Na pásku 1 si uložíme a písmen „a“. (Pokud násobíme 3*5, bude tam třikrát písmeno „a“.)
  2. Pokud na pásce 1 nejsou označena všechna písmena „a“, zapiš na pásku 2 tolik „b“, jakou má b hodnotu. (Pokud násobíme 3*5, zapíšeme tam pětkrát „b“.) V opačném případě ukonči výpočet, na pásce je tolik symbolů „b“, kolik je a*b.
  3. Označ jeden symbol „a“ na pásce 1. (Označit symbol „a“ můžeme například tak, že ho přepíšeme na symbol „x“.)
  4. Vrať se k bodu 2.

Ukázka výpočtu pro vstup 3*5:

  1. Zapíšeme na pásku 1: aaa.
  2. Na pásce 1 jsou neoznačená „a“, takže zapíšeme na pásku pětkrát „b“: páska 2: bbbbb.
  3. Na první pásce označíme jedno áčko: xaa.
  4. Na pásce 1 jsou neoznačená „a“, takže zapíšeme na pásku pětkrát „b“: páska 2: bbbbbbbbbb.
  5. Na první pásce označíme jedno áčko: xxa.
  6. Na pásce 1 jsou neoznačená „a“, takže zapíšeme na pásku pětkrát „b“: páska 2: bbbbbbbbbbbbbbb.
  7. Na první pásce označíme jedno áčko: xxx.
  8. Na pásce 1 nejsou neoznačená „a“, výpočet končí. Na pásce 2 máme patnáct symbolů „b“.

Související články[editovat | editovat zdroj]