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

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 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

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 [math]\displaystyle{ L^* }[/math] nad jezikom L
• nadovezivanje (konkatenacija) [math]\displaystyle{ L \circ P }[/math] jezika L i P
• unija [math]\displaystyle{ L \cup P }[/math]
• presjek [math]\displaystyle{ L \cap P }[/math]

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

• Rekurzivni jezik

Vanjske poveznice

• Complexity Zoo: RE

Izvori

• 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