Rekurzivno prebrojiv jezik

Izvor: Wikipedija

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.

[uredi] Definicije

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

Rekurzivno prebrojiv formalni jezik je rekurzivno prebrojiv podskup skupa svih mogućih riječi nad abecedom jezika.
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".
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.

[uredi] Svojstva zatvorenosti

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 $L *$ nad jezikom L
nadovezivanje (konkatenacija) $L \circ P$ jezika L i P
unija $L \cup P$
presjek $L \cap P$

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.

[uredi] Vidjeti također

Rekurzivni jezik

[uredi] Vanjske poveznice

Complexity Zoo: RE

[uredi] Reference

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.