Rekurzivní jazyk - Recursive language

v matematika, logika a počítačová věda, a formální jazyk (A soubor konečných posloupností symboly převzato z pevné abeceda ) je nazýván rekurzivní pokud je to rekurzivní podmnožina množiny všech možných konečných posloupností nad abecedou jazyka. Ekvivalentně je formální jazyk rekurzivní, pokud existuje a celkem Turingův stroj (A Turingův stroj který se zastaví pro každý daný vstup), který, když dostane konečnou posloupnost symbolů jako vstup, přijme jej, pokud patří do jazyka, a odmítne jej jinak. Rekurzivní jazyky se také nazývají rozhodnutelné.

Koncept rozhodnutelnost lze rozšířit na další modely výpočtu. Například lze hovořit o jazycích, o kterých lze rozhodnout v a nedeterministický Turingův stroj. Proto, kdykoli je možná nejednoznačnost, je použito synonymum pro „rekurzivní jazyk“ Turing-rozhodnutelný jazykspíše než jednoduše rozhodnutelné.

Třída všech rekurzivních jazyků se často nazývá R, i když se tento název také používá pro třídu RP.

Tento typ jazyka nebyl v Chomského hierarchie z (Chomsky 1959 ). Všechny rekurzivní jazyky jsou také rekurzivně spočetné. Všechno pravidelný, bez kontextu a kontextové jazyky jsou rekurzivní.

Definice

Pro koncept rekurzivního jazyka existují dvě ekvivalentní hlavní definice:

Rekurzivní formální jazyk je a rekurzivní podmnožina v soubor všech možných slov přes abeceda z Jazyk.
Rekurzivní jazyk je formální jazyk, pro který existuje a Turingův stroj že když je předložen s jakýmkoli konečným vstupem tětiva, zastaví a přijme, pokud je řetězec v jazyce, a zastaví a odmítne jinak. Turingův stroj se vždy zastaví: je známý jako a rozhodující a říká se rozhodni se rekurzivní jazyk.

Podle druhé definice libovolné rozhodovací problém lze prokázat, že je rozhodnutelný vystavením algoritmus protože to končí na všech vstupech. An nerozhodnutelný problém je problém, o kterém nelze rozhodnout.

Příklady

Jak je uvedeno výše, každý kontextově citlivý jazyk je rekurzivní. Jednoduchým příkladem rekurzivního jazyka je tedy množina L = {abc, aabbcc, aaabbbccc, ...}; formálněji sada

{displaystyle L = {, win {a, b, c} ^ {*} uprostřed w = a ^ {n} b ^ {n} c ^ {n} {mbox {pro některé}} ngeq 1,}}

je kontextově citlivý, a proto rekurzivní.

Je obtížnější popsat příklady rozhodovatelných jazyků, které nejsou kontextově citlivé. Pro jeden takový příklad, nějaká znalost s matematická logika je požadováno: Presburgerova aritmetika je teorie prvního řádu přirozených čísel sčítáním (ale bez násobení). Zatímco sada dobře formulované vzorce v Presburgerově aritmetice je bezkontextová, každý deterministický Turingův stroj přijímající množinu pravdivých výroků v Presburgerově aritmetice má nejhorší runtime minimálně ${displaystyle 2 ^ {2 ^ {cn}}}$ , pro nějakou konstantu C>0 (Fischer a Rabin 1974 ). Tady, n označuje délku daného vzorce. Protože každý kontextově citlivý jazyk může být přijat a lineárně ohraničený automat, a takový automat lze simulovat deterministickým Turingovým strojem s nejhorší dobou chodu ${displaystyle c ^ {n}}$ pro nějakou konstantu C^{[Citace je zapotřebí ]}, sada platných vzorců v Presburgerově aritmetice není kontextová. Na pozitivní straně je známo, že existuje deterministický Turingův stroj běžící v čase maximálně trojnásobně exponenciálně n která určuje množinu skutečných vzorců v Presburgerově aritmetice (Oppen 1978 ). Toto je tedy příklad jazyka, který je rozhodnutelný, ale není citlivý na kontext.

Vlastnosti uzavření

Rekurzivní jazyky jsou Zavřeno v rámci následujících operací. To je, pokud L a P jsou dva rekurzivní jazyky, pak jsou rekurzivní také následující jazyky:

The Kleene hvězda ${displaystyle L ^ {*}}$
Obraz φ (L) pod e-free homomorfismus φ
Zřetězení ${displaystyle Lcirc P}$
Unie ${displaystyle Lcup P}$
Křižovatka ${displaystyle Lcap P}$
Doplněk ${displaystyle L}$
Nastavený rozdíl ${displaystyle L-P}$

Poslední vlastnost vyplývá ze skutečnosti, že nastavený rozdíl lze vyjádřit pomocí průniku a doplnění.

Viz také

Reference

Michael Sipser (1997). "Rozhodnutelnost". Úvod do teorie výpočtu. PWS Publishing. str.151–170. ISBN 978-0-534-94728-6.CS1 maint: ref = harv (odkaz)
Chomsky, Noam (1959). „O určitých formálních vlastnostech gramatik“. Informace a kontrola. 2 (2): 137–167. doi:10.1016 / S0019-9958 (59) 90362-6.CS1 maint: ref = harv (odkaz)
Fischer, Michael J.; Rabin, Michael O. (1974). „Superexponenciální složitost Presburgerovy aritmetiky“. Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.CS1 maint: ref = harv (odkaz)
Oppen, Derek C. (1978). „A 2^{2^{2^pn}} Horní hranice složitosti Presburgerovy aritmetiky “. J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1.