Gramatika neograničenih produkcija: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
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>.
#
# Usporedi rezultirajući rečenični oblik na drugoj traci sa riječi na prvoj traci.
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.
|