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 pobrojati sve valjane nizove znakova jezika. Uočimo da, ukoliko je jezik beskonačan, dani algoritam pobrojavanja može biti odabran tako da izbjegava ponavljanja, budući da 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 ukoliko 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 sa 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

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.