Rekurzivní jazyk

Formální jazyk L je rekurzivní, pokud existuje Turingův stroj (dále TS), který akceptuje právě slova z tohoto jazyka, a jehož výpočet nad libovolným řetězcem skončí po konečném počtu kroků. Pokud takový TS M existuje, říkáme, že TS M rozhoduje jazyk L. Každý rekurzivní jazyk je také rekurzivně spočetný, ale existují rekurzivně spočetné jazyky, které nejsou rekurzivní.

Uzávěrové vlastnosti

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í

Máme-li jazyky L₁ a L₂, které jsou rekurzivní, existují i TS M₁ a M₂, které tyto jazyky rozhodují. Sestrojíme-li sjednocení jazyků L₁ a L₂, vznikne nám nový jazyk L_s. Tento nový jazyk L_s bude rozhodován TS M_s, který bude pro slovo w postupovat takto:

Simuluj TS M₁ pro slovo w. Pokud TS M₁ slovo přijme, přijmi slovo. Pokud odmítne, pokračuj dále.
Simuluj TS M₂ pro slovo w. Pokud TS M₂ slovo přijme, přijmi slovo. Pokud odmítne, odmítni slovo w.

Vzhledem k tomu, že oba TS M₁ i M₂ 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

Máme-li jazyky L₁ a L₂, které jsou rekurzivní, existují i TS M₁ a M₂, které tyto jazyky rozhodují. Sestrojíme-li průnik jazyků L₁ a L₂, vznikne nám nový jazyk L_p. Tento nový jazyk L_p bude rozhodován TS M_p, který bude pro slovo w postupovat takto:

Simuluj TS M₁ pro slovo w. Pokud TS M₁ slovo odmítne, odmítni slovo. Pokud přijme, pokračuj dále.
Simuluj TS M₂ pro slovo w. Pokud TS M₂ 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

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:

Simuluj činnost TS M pro vstup w.
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í

Zřetězením dvou rekurzivních jazyků L₁ a L₂ vznikne nový jazyk L_z, který obsahuje slova vzniklá zřetězením (spojením) všech slov z L₁ se všemi slovy z L₂. Příklad: L₁ = {ab, abc}, L₂ = {cd, de}. L_z = {abcd, abde, abccd, abcde}. Nyní bychom potřebovali nějaký algoritmus, který by zjistil, zda dané slovo patří do L_z. 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 L_z, stačí nám najít taková slova m, n, pro která platí m+n=w a zároveň m je z L₁ a n z L₂. TS Z, který bude rozhodovat, zda w patří do L_z, pak bude postupovat takto (TS M₁ rozhoduje L₁ a M₂ rozhoduje L₂):

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\}$ .
Prozkoumej všechny dvojice v R. Aktuálně procházenou dvojici označme D.
1. Simuluj TS M₁ pro D_m. Pokud M₁ odmítá, jdi zkusit další dvojici.
2. Simuluj TS M₂ pro D_n. Pokud M₂ odmítá, jdi zkusit další dvojici. Pokud přijímá, TS Z přijímá slovo w.
TS Z odmítá slovo w.

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

Příklad Rekurzivního jazyka

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.

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“.)
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.
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“.)
Vrať se k bodu 2.

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

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

Vztah rekurzivních jazyků k ostatním třídám jazyků

Třída rekurzivních jazyků je vlastní podtřídou třídy rekurzivně spočetných jazyků, tj. každý rekurzivní jazyk je také rekurzivně spočetný, ale existují rekurzivně spočetné jazyky, které nejsou rekurzivní. Toto tvrzení nelze zjednodušit na „rekurzivní jazyk je podmnožinou rekurzivně spočetného jazyka“, protože se nejedná o velikost jazyka (tj. „počet“ řetězců, které do něho patří), ale spíše o jemnost stanovení hranic jazyka.

Každý konečný jazyk (obsahující konečný počet řetězců) je rekurzivním jazykem.

Každý regulární jazyk (jazyk typu 3) je rekurzivním jazykem.

Každý bezkontextový jazyk (jazyk typu 2) je rekurzivním jazykem.

Každý kontextový jazyk (jazyk typu 1) je rekurzivním jazykem.