Rekurzivno prebrojiv jezik

U matematici, logici i računarstvu, rekurzivno prebrojiv jezik je tip formalnog jezika koji se takođe naziva i parcijalno odlučivim ili Tjuring-prepoznatljivim. Poznat je kao jezik tipa 0 u hijerarhiji Čomskog koja kategorije formalne jezike. Klasa svih rekurzivno prebrojivih jezika se naziva RE.

Definicije

Postoje tri ekvivalentne glavne definicije za koncept rekurzivno prebrojivog jezika.

1. Rekurzivno prebrojiv formalni jezik je rekurzivno prebrojiv podskup u skupu svih mogućih reči nad azbukom jezika.
2. Rekurzivno prebrojiv jezik je formalni jezik za koji postoji Tjuringova mašina (ili neka druga izračunljiva funkcija) koja može da prebroji sve validne niske jezika. Treba imati u vidu da ako je jezik beskonačan, izabrani algoritam za prebrojavanje može da bude izabran tako da izbegava ponavljanja, jer je moguće testirati da li je niska koja je dobijena za broj n već proizvedena za neki broj manji od n. Ako jeste, onda se računa izlaz za ulaz n+1 umesto za n (rekurzivno), ali se opet proverava da li je taj broj nov.
3. Rekurzivno prebrojiv jezik je formalni jezik za koji postoji Tjuringova mašina (ili neka druga izračunljiva funkcija) koja će se zaustaviti i prihvatiti svaku reč jezika, a ili se zaustaviti i odbaciti ili beskonačno raditi za svaku reč koja ne pripada jeziku. Suprotnost ovome su rekurzivni jezici, kod kojih se zahteva da se Tjuringova mašina zaustavlja u svim slučajevima.

Svi regularni, kontekstno-slobodni, kontekstno-senzitivni i rekurzivni jezici su rekurzivno prebrojivi.

Postova teorema pokazuje da RE, zajedno sa svojim komplementom co-RE, odgovara prvom stepenu aritmetičke hijerarhije.

Svojstva zatvorenja

Rekurzivno prebrojivi jezici su zatvoreni za sledeće operacije. To jest, ako su L i P dva rekurzivno prebrojiva jezika, onda su i sledeći jezici rekurzivno prebrojivi:

• Klinijeva zvezda $L^{*}$ nad L
• Konkatenacija $L\circ P$ L i P
• unija $L\cup P$
• presek $L\cap P$

Treba imati u vidu da rekurzivno prebrojivi jezici nisu zatvoreni za razliku skupova ili komplement. Razlika skupova L\P može ali ne mora da bude rekurzivno prebrojiva. Ako je L rekurzivno prebrojiv onda je komplement od L rekurzivno prebrojiv ako i samo ako je L ujedno i rekurzivan.

Vidi još

• Rekurzivni jezik

Spoljašnje veze

• Klase RE na sajtu Complexity Zoo

Literatura

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springer.