Třinácté cvičení (17. 5.)

Příklad – simulátor Turingova stroje

Napište simulátor Turingova stroje (vysvětlení funkce TS na tabuli).

Program načte definici TS, vypíše prompt a čeká na instrukce. Počáteční obsah pásky je předán simulátoru jako parametr na příkazové řádce. Jednotlivá pole pásky jsou oddělena mezerami a pole, kde začíná hlava je ohraničeno znaky < a >. Ovládání výpočtu:

1. <Enter> provedení jednoho kroku výpočtu a vypsání aktuálního stavu a pásky
2. r (run); běh výpočtu až do konce, nebo do stisku Ctrl-C; při stisku Ctrl-C se dokončí aktuálně prováděný krok a je znovu nabídnut prompt
3. Ctrl-D ukončení simulace

Příklad Turingova stroje

Q={q0,q1,q2,q3,q4,q5,q6,q7}
G={0,1,b}
s=q0
F={q7}
d(q0,0) = (q1,b,R)
d(q1,0) = (q1,0,R)
d(q1,1) = (q2,1,R)
d(q2,1) = (q2,1,R)
d(q2,b) = (q3,b,L)
d(q3,1) = (q4,b,L)
d(q4,b) = (q7,b,R)
d(q4,1) = (q5,1,L)
d(q5,1) = (q5,1,L)
d(q5,0) = (q6,0,L)
d(q6,0) = (q6,0,L)
d(q6,b) = (q0,b,R)

Testovací vstupy

./ts "<0> 0 0 0 1 1 1 1"
./ts "<0> 0 0 1 0 1 1 1"
./ts "<0> 0 0 1 1"