Rekurzivno prebrojiv jezik

U matematici, logici i računarstvu, rekurzivno prebrojiv jezik je tip formalnog jezika koji se još zove i parcijalno odlučiv ili Turing-prepoznatljiv. Poznat je kao jezik tipa 0 u Chomskyjevoj hijerarhiji formalnih jezika. Klasa rekurzivno prebrojivih jezika je poznata kao klasa složenosti RE.

Definicije

uredi

U literaturi su prisutne tri glavne istovjetne definicije koncepta rekurzivno prebrojivog jezika.

  1. Rekurzivno prebrojiv formalni jezik je rekurzivno prebrojiv podskup skupa svih mogućih riječi nad abecedom jezika.
  2. Rekurzivno prebrojiv jezik je formalni jezik za koji postoji Turingov stroj (ili neka druga izračunljiva funkcija) koji može prebrojiti sve valjane nizove znakova jezika. Uočimo da, ako je jezik beskonačan, dani algoritam prebrojavanja može biti odabran tako da izbjegava ponavljanja, jer možemo provjeriti je li niz znakova proizveden za broj n "već prije" proizveden za broj manji od n. Ako je već prije proizveden, koristimo izlaz za ulaz za broj n+1 mjesto njega (rekurzivno), ali opet, provjeravamo je li "novi".
  3. Rekurzivno prebrojiv jezik jest formalni jezik za kojeg postoji Turingov stroj (ili neka druga izračunljiva funkcija) koji će stati i prihvatiti ako primi bilo koji niz znakova koji je element jezika kao ulaz, a inače može stati i ne prihvatiti niz ili se vrtjeti u beskonačnoj petlji u slučaju ulaza niza znakova koji nije u jeziku. Kontrastirajmo ovo s rekurzivnim jezicima, koji zahtijevaju da Turingov stroj stane u svim slučajevima.

Svi regularni, kontekstno neovisni, kontekstno ovisni i rekurzivni jezici su rekurzivno prebrojivi.

RE, skupa sa svojim komputacijskim komplementom co-RE, čini okosnicu aritmetičke hijerarhije.

Svojstva zatvorenosti

uredi

Rekurzivno prebrojivi jezici su zatvoreni nad sljedećim operacijama. To jest, ako su L i P dva rekurzivno prebrojiva jezika, tada su sljedeći jezici također rekurzivno prebrojivi:

  • Kleeneov operator   nad jezikom L
  • nadovezivanje (konkatenacija)   jezika L i P
  • unija  
  • presjek  

Uočimo da rekurzivno prebrojivi jezici nisu zatvoreni nad razlikom ili komplementom. Razlika jezika L\P kao i komplement jezika L mogu ali i ne moraju biti rekurzivno prebrojivi jezici.

Vidjeti također

uredi

Vanjske poveznice

uredi

Izvori

uredi
  • Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3
  • Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X
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.