|
[b]Zadatak.[/b] Na traci Turingovog stroja nalazi se niz znakova iz skupa [latex]S = \left\{a,\, b,\, c\right\}[/latex], pri čemu se svaki znak može pojaviti nula ili više puta. Konstruirajte Turingov stroj koji ispred svakog znaka "[latex]b[/latex]" dodaje znak "[latex]x[/latex]". Pri tome niti jedan znak ne smije biti izbrisan.
[b]Rješenje.[/b] U početku neka je glava pozicirana na najdesnijem znaku u nizu. Ukoliko ne postoji niti jedan znak na traci, neka se glava nalazi bilo gdje na traci. Sada se krećemo prema početku niza. Ukoliko naiđemo na znak "[latex]b[/latex]", iza njega ćemo upisati znak "[latex]x[/latex]", te sve znakove iza pomaknuti za jedno mjesto u lijevo. Zatim se vraćamo na upisani znak "[latex]x[/latex]", te se ponašamo kao da je znak prije njega u nizu zapravo kraj rječi koja se nalazi lijevo od toga [latex]x[/latex]-a. Rješenje ću napisati pomoću funkcijskog zapisa. Imajmo na umu da se krećemo u lijevo, dakle, čitati ćemo rječ s desna na lijevo.
[latex]\delta\left(q_0,\, \_\right) = \left(q_{\textrm{f}},\, \_,\, \textrm{S}\right)[/latex]
Ukoliko na traci ne postoji niti jedan znak ili ako nema više znakova "[latex]b[/latex]" onda smo gotovi.
[latex]\delta\left(q_0,\, z\right) = \left(q_0,\, z,\, \textrm{L}\right)[/latex], gdje je [latex]z \in \left\{a,\, c\right\}[/latex]
Glava "prelazi" preko svih znakova "[latex]a[/latex]" i "[latex]c[/latex]" jer nam oni nisu "zanimljivi".
[latex]\delta\left(q_0,\, b\right) = \left(q_x,\, b,\, \textrm{L}\right)[/latex]
Naišli smo na znak "[latex]b[/latex]".
[latex]\delta\left(q_x,\, z\right) = \left(q_z,\, x,\, \textrm{L}\right)[/latex], gdje je [latex]z \in \left\{a,\, b,\, c\right\}[/latex]
Nakon tog znaka "[latex]b[/latex]" (ako se nakon njega nalazi još koji znak) stavljamo znak "[latex]x[/latex]".
[latex]\delta\left(q_x,\, \_\right) = \left(q_{\textrm{f}},\, x,\, \textrm{S}\right)[/latex]
Ukoliko je taj znak "[latex]b[/latex]" prvi u rječi, tj. zadnji gledano s desna (jer se tako krećemo), onda prije njega (na prazno mjesto) upisujemo znak "[latex]x[/latex]" i gotovi smo.
[latex]\delta\left(q_z,\, z'\right) = \left(q_{z'},\, z,\, \textrm{L}\right)[/latex], gdje su [latex]z,\, z' \in \left\{a,\, b,\, c\right\}[/latex]
"Standardni" postupak pomicanja svih znakova za jedno mjesto u lijevo.
[latex]\delta\left(q_z,\, \_\right) = \left(q_{\textrm{n}},\, z,\, \textrm{D}\right)[/latex], gdje je [latex]z \in \left\{a,\, b,\, c\right\}[/latex]
Kada prilikom pomicanja znakova u lijevo naiđemo na razmak, upišemo znak koji trebamo upisati te se pomaknemo za jedno mjesto u desno. Sad se počinjemo vraćati do znaka "[latex]x[/latex]" kojeg smo zadnjeg upisali.
[latex]\delta\left(q_{\textrm{n}},\, z\right) = \left(q_{\textrm{n}},\, z,\, \textrm{D}\right)[/latex], gdje je [latex]z \in \left\{a,\, b,\, c\right\}[/latex]
Krećemo se od početka rječi prema prvom znaku "[latex]x[/latex]" na kojega naiđemo.
[latex]\delta\left(q_{\textrm{n}},\, x\right) = \left(q_0,\, x,\, \textrm{L}\right)[/latex]
Naišli smo na "[latex]x[/latex]" kojeg smo zadnjeg upisali, pozicioniramo glavu na znak prije tog znaka "[latex]x[/latex]" i dalje se ponašamo kao da je taj znak nad kojim se glava nalazi zapravo zadnji znak u rječi.
Nadam se da je dobro... :-), te da sam dovoljno objasnio... :-)
Zadatak. Na traci Turingovog stroja nalazi se niz znakova iz skupa  , pri čemu se svaki znak može pojaviti nula ili više puta. Konstruirajte Turingov stroj koji ispred svakog znaka " " dodaje znak " ". Pri tome niti jedan znak ne smije biti izbrisan.
Rješenje. U početku neka je glava pozicirana na najdesnijem znaku u nizu. Ukoliko ne postoji niti jedan znak na traci, neka se glava nalazi bilo gdje na traci. Sada se krećemo prema početku niza. Ukoliko naiđemo na znak "", iza njega ćemo upisati znak "", te sve znakove iza pomaknuti za jedno mjesto u lijevo. Zatim se vraćamo na upisani znak "", te se ponašamo kao da je znak prije njega u nizu zapravo kraj rječi koja se nalazi lijevo od toga -a. Rješenje ću napisati pomoću funkcijskog zapisa. Imajmo na umu da se krećemo u lijevo, dakle, čitati ćemo rječ s desna na lijevo.
Ukoliko na traci ne postoji niti jedan znak ili ako nema više znakova "" onda smo gotovi.
 , gdje je 
Glava "prelazi" preko svih znakova " " i " " jer nam oni nisu "zanimljivi".
Naišli smo na znak "".
 , gdje je 
Nakon tog znaka "" (ako se nakon njega nalazi još koji znak) stavljamo znak "".
Ukoliko je taj znak "" prvi u rječi, tj. zadnji gledano s desna (jer se tako krećemo), onda prije njega (na prazno mjesto) upisujemo znak "" i gotovi smo.
 , gdje su 
"Standardni" postupak pomicanja svih znakova za jedno mjesto u lijevo.
 , gdje je
Kada prilikom pomicanja znakova u lijevo naiđemo na razmak, upišemo znak koji trebamo upisati te se pomaknemo za jedno mjesto u desno. Sad se počinjemo vraćati do znaka "" kojeg smo zadnjeg upisali.
 , gdje je
Krećemo se od početka rječi prema prvom znaku "" na kojega naiđemo.
Naišli smo na "" kojeg smo zadnjeg upisali, pozicioniramo glavu na znak prije tog znaka "" i dalje se ponašamo kao da je taj znak nad kojim se glava nalazi zapravo zadnji znak u rječi.
Nadam se da je dobro...  , te da sam dovoljno objasnio...
|
