Rekurzivni jezik
Izvor: Wikipedija
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 definiran u Chomskyjevoj hijerarhiji.
[uredi] Definicije
U literaturi prevladavaju dvije istovjetne definicije koncepta rekurzivnog jezika:
- Rekurzivni formalni jezik je rekurzivni podskup skupa svih mogući riječi nad abecedom jezika.
- Rekurzivni jezik je formalni jezik za kojeg postoji Turingov stroj koji će, za svaki ulazni niz znakova (simbola) stati i prihvatiti niz ukoliko je on element jezika, a inače ga neće prihvatiti. Turingov stroj uvijek staje - poznat i pod nazivom odlučitelj - i kažemo da odlučuje rekurzivni jezik.
Svi rekurzivni jezici su rekurzivno prebrojivi. Svi regularni, kontekstno neovisni i kontekstno ovisni jezici su rekurzivni.
[uredi] Svojstva zatvorenosti
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 L * jezika L
- neprebrisujući homeomorfizam φ(L) jezika L
- nadovezivanje (konkatenacija)
jezika L i jezika P
- unija
- presjek
- komplement jezika L
- razlika L − P
Posljednje svojstvo slijedi iz činjenice da se razlika skupova može izraziti preko presjeka i komplementa.
[uredi] Reference
- Michael Sipser (1997). “Decidability”, Introduction to the Theory of Computation, 151–170, PWS Publishing. ISBN 0-534-94728-X.
- Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X.
- Siniša Srbljić (2003). Jezični procesori 1, Element. ISBN 953-197-129-3.
- Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167.
Teorija automata: formalni jezici i formalne gramatike | |||
---|---|---|---|
Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
Tip 3 | Regularna | Regularni | Konačni |
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. |