Rekurzivni jezik

Izvor: Wikipedija
Skoči na: orijentacija, traži

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.

Definicije[uredi VE | uredi]

U literaturi prevladavaju dvije istovjetne definicije koncepta rekurzivnog jezika:

  1. Rekurzivni formalni jezik je rekurzivni podskup skupa svih mogući riječi nad abecedom jezika.
  2. 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.

Svojstva zatvorenosti[uredi VE | 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 L^* jezika L
  • neprebrisujući homeomorfizam φ(L) jezika L
  • nadovezivanje (konkatenacija) L \circ P jezika L i jezika P
  • unija L \cup P
  • presjek L \cap P
  • komplement jezika L
  • razlika L - P

Posljednje svojstvo slijedi iz činjenice da se razlika skupova može izraziti preko presjeka i komplementa.

Izvori[uredi VE | uredi]

  • Michael Sipser (1997). “Decidability”, Introduction to the Theory of Computation, str. 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.