Rekurzivní jazyk

V matematické logice a informatice , rekurzivní jazyk je druh formálního jazyka , také volal decidable , nebo Turing decidable . Třída všech rekurzivních jazyků je často označována R , ačkoli stejné označení se používá pro třídu RP .

Tento typ jazyka není v Chomského hierarchii definován ( Chomsky 1959 ).

Definice

Používají se dvě ekvivalentní definice rekurzivního jazyka:

1. Formální rekurzivní jazyk je rekurzivní podmnožina souboru všech možných slov v abecedě formálního jazyka .
2. Rekurzivní jazyk je formální jazyk, pro který existuje Turingův stroj , který se zastaví na libovolném vstupním řetězci a povolí jej tehdy a jen tehdy, pokud do jazyka patří. Takový stroj je prý řešitel a řeší daný rekurzivní jazyk.

Všechny rekurzivní jazyky jsou také rekurzivně vyčíslitelné . Všechny běžné , bezkontextové a kontextově citlivé jazyky jsou rekurzivní.

Vlastnosti uzávěru

Rekurzivní jazyky jsou uzavřeny v následujících operacích. Pokud jsou tedy L a P rekurzivní jazyky, pak jsou rekurzivní také následující jazyky:

• Kleene uzávěr ;
• obraz , kde je homomorfismus takový, že , kde je prázdný řetězec;
• zřetězení ;
• sdružení ;
• křižovatka ;
• sčítání ;
• rozdíl .

Reference

• Michael Sipser Rozhodnutelnost // Úvod do teorie  počítání . - PWS Publishing, 1997. - S.  151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. O určitých formálních vlastnostech gramatik   // Information and Control : deník. - 1959. - Sv. 2 , ne. 2 . - S. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Viz také

• Rekurzivně vyčíslený jazyk