Rekurzivno prebrojiv jezik: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
m + predložak tablice Chomskyjeve hijerarhije
m interwiki
Redak 5:
U literaturi su prisutne tri glavne istovjetne definicije koncepta rekurzivno prebrojivog jezika.
 
# Rekurzivno prebrojiv formalni jezik je [[rekurzivno prebrojiv skup|rekurzivno prebrojiv]] podskup skupa[[skup]]a svih mogućih riječi nad [[abeceda(računarstvo)|abecedom]] [[formalni jezik|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 [[rekurzivni jezik|rekurzivnim jezicima]], koji zahtijevaju da Turingov stroj stane u svim slučajevima.