IB102 – úkol 9, příklad 2 Odevzdání: 7. 12. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] Mějme Turingův stroj M = (Q, Σ, Γ, , , δ, q0, qaccept , qreject ), kde
Q = {q0, qA, q, qr, qback , qaccept , qreject },
Σ = {a, b},
Γ = { , , X, a, b}
a přechodová funkce δ je určena následující tabulkou:
X a b
q0 (q0, , R) (qaccept , , R) (qaccept , X, R) (qA, X, R) (q, X, R)
qA (qA, , R) (qaccept , , R) (qaccept , X, R) (q, a, R) (q, b, R)
q (q, , R) (qr, , L) (qr, X, L) (q, a, R) (q, b, R)
qr (qr, , R) (qr, , R) (qreject , X, L) (qback , X, L) (qback , X, L)
qback (qback , , R) (qback , , R) (q0, X, R) (qback , a, L) (qback , b, L)
a) Napište výpočet Turingova stroje M na vstupním slově baaba. Výpočet pište jako
posloupnost konfigurací, kde každé dvě po sobě následující konfigurace jsou v relaci
krok výpočtu.
b) Najděte slovo délky alespoň 3, které stroj M zamítá, a napište výpočet stroje M nad
tímto slovem.