Rekurzivni jezik
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
U matematici, logici i računarstvu, rekurzivni jezik je tip formalnog jezika koji se još zove i rekurzivan, odlučiv ili Turing-odlučiv. Klasa svih rekurzivnih jezika se često zove R, iako je to ime često korišteno i za klasu složenosti RP.
Ovaj tip jezika nije definisan u Chomskyjevoj hijerarhiji.
Definicije uredi
U literaturi prevladavaju dvije definicije koncepta rekurzivnog jezika:
- Rekurzivni formalni jezik je rekurzivni podskup skupa svih mogućih riječi nad abecedom jezika.
- Rekurzivni jezik je formalni jezik za kojeg postoji Turingova mašina koja će, za svaki ulazni niz znakova (simbola) stati i prihvatiti niz ukoliko je on element jezika, a inače ga neće prihvatiti. Turingova mašina uvijek staje - poznata i pod nazivom odlučitelj - i kažemo da odlučuje rekurzivni jezik.
Svi rekurzivni jezici su rekurzivno prebrojivi. Svi regularni, kontekstno nezavisni i kontekstno zavisni jezici su rekurzivni.
Svojstva zatvorenosti uredi
Rekurzivni su jezici zatvoreni nad sljedećim operacijama. To jest, ako su L i P dva rekurzivna jezika, tada su i sljedeći jezici također rekurzivni:
- Kleeneov operator jezika L
- neprebrisujući homeomorfizam φ(L) jezika L
- nadovezivanje (konkatenacija) jezika L i jezika P
- unija
- presjek
- komplement jezika L
- razlika
Posljednje svojstvo slijedi iz činjenice da se razlika skupova može izraziti preko presjeka i komplementa.
Reference uredi
- Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X