Gramatika neograničenih produkcija: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
Addbot (razgovor | doprinosi)
m Bot: brisanje 7 međuwiki poveznica premještenih u stranicu d:q602934 na Wikidati
mNema sažetka uređivanja
Redak 11:
# Započinje rad na krajnje lijevom kraju druge trake i potom ponavljajuće odabire pomak udesno ili odabire trenutnu poziciju na traci.
# Nedeterministički odabire produkciju <math>\beta \to \gamma</math> iz skupa produkcija gramatike <math>G</math>.
# Ukolikoako se <math>\beta</math> pojavi na nekoj poziciji druge trake, zamijeni <math>\beta</math> sa <math>\gamma</math>, uz mogući posmak znakova trake lijevo ili desno ovisno o relativnim duljinama <math>\beta</math> i <math>\gamma</math> (tj. ako je <math>\beta</math> dulji od <math>\gamma</math>, obavi posmak znakova trake ulijevo).
# Usporedi rezultirajući rečenični oblik na drugoj traci sa riječi na prvoj traci. UkolikoAko odgovaraju, tada Turingov stroj prihvaća riječ. UkolikoAko ne odgovaraju, vrati se na prvi korak.
 
Lako se vidi da će ovaj Turingov stroj generirati sve i samo rečenične oblike gramatike <math>G</math> na drugoj traci nakon što je posljednji korak izvršen proizvoljan broj puta, i time jezik <math>L(G)</math> mora biti rekurzivno prebrojiv.