Rekurzivni jezik

Rekurzivni jezik u matematici, logici i računarstvu je tip formalnog jezika koji se još naziva i odlučivim ili Tjuring-odlučivim. Klasa svih rekurzivnih jezika see često naziva R, mada se ovo ime koristi i za klasu RP.

Ovaj tip jezika nije definisan u hijerarhiji Čomskog Chomsky 1959.

Definicije

Postoje dve glavne ekvivalentne definicije za koncept rekurzivnog jezika:

1. Rekurzivni formalni jezik je rekurzivan podskup u skupu svih mogućih reči nad azbukom jezika.
2. Rekurzivni jezik je formalni jezik za koji postoji Tjuringova mašina koja će kada joj se da bilo koja ulazna niska da stane i prihvati nisku ako ona pripada jeziku, a da stane i odbaci nisku u suprotnom. Tjuringova mašina se uvek zaustavlja; poznata je kao odlučivač, i kaže se da ona odlučuje rekurzivni jezik.

Svi rekurzivni jezici su i rekurzivno prebrojivi. Svi regularni, kontekstno-slobodni i kontekstno-senzitivni jezici su rekurzivni.

Svojstva zatvorenja

Rekurzivni jezici su zatvoreni u odnosu na sledeće operacije. Drugim rečima, ako su L i P dva rekurzivna jezika, onda su i sledeći jezici rekurzivni:

• Klinijeva zvezda $L^{*}$
• slika od φ(L) u odnosu na e-slobodni homomorfizam φ
• konkatenacija $L\circ P$
• unija $L\cup P$
• presek $L\cap P$
• komplement od L
• razlika skupova $L-P$

Poslednje svojstvo sledi iz činjenice da se razlika skupova može izraziti pomoću preseka i komplementa.

Vidi još

• Rekurzivno prebrojiv jezik
• Rekurzija
• Rekurzivni akronim

Literatura

• Sipser, Michael (1997). „Decidability”. Introduction to the Theory of Computation. PWS Publishing. str. 151–170. ISBN 978-0-534-94728-6. 
• Chomsky, Noam (1959). „On certain formal properties of grammars”. Information and Control. 2 (2): 137—167. doi:10.1016/S0019-9958(59)90362-6.