From Wikipedia, the free encyclopedia
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í.
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í.
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:
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.
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:
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.
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:
Nový TS M' bude jednoduše vracet přesně opačné výsledky, než původní TS M. Tento TS M' rozhoduje jazyk L'.
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):
Poznámka na konec: TS M1 i M2 rozhodují své jazyky, takže se nikdy nezacyklí.
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.
Ukázka výpočtu pro vstup 3*5:
aaa
.bbbbb
.xaa
.bbbbbbbbbb
.xxa
.bbbbbbbbbbbbbbb
.xxx
.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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.