IB102 – úkol 9, příklad 2 – řešení 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.
a) Připomeňme, že konfigurace Turingova stroje je definována jako trojice (q, z, n) ∈
Q×{y ω
| y ∈ Γ∗
}×N0, kde q je aktuální stav, y ω
je obsah pásky a n je pozice hlavy
na pásce (viz 9. přednáška, slajd 2). Relace krok výpočtu ( ) je definována na 3. slajdu
9. přednášky. Výpočet nad slovem baaba tedy začíná v konfiguraci (q0, baaba ω
, 0).
(q0, baaba ω
, 0) (q0, baaba ω
, 1) (q, Xaaba ω
, 2)
(q, Xaaba ω
, 3) (q, Xaaba ω
, 4)
(q, Xaaba ω
, 5) (q, Xaaba ω
, 6)
(qr, Xaaba ω
, 5) (qback , XaabX ω
, 4)
(qback , XaabX ω
, 3) (qback , XaabX ω
, 2)
(qback , XaabX ω
, 1) (q0, XaabX ω
, 2)
(qA, XXabX ω
, 3) (q, XXabX ω
, 4)
(q, XXabX ω
, 5) (qr, XXabX ω
, 4)
(qback , XXaXX ω
, 3) (qback , XXaXX ω
, 2)
(q0, XXaXX ω
, 3) (qA, XXXXX ω
, 4)
(qaccept , XXXXX ω
, 5)
A tedy stroj M slovo baaba akceptuje.
IB102 – úkol 9, příklad 2 – řešení Odevzdání: 7. 12. 2015
Vypracoval(a): UČO:
Skupina:
b) Z předchozího výpočtu a definice přechodové funkce Turingova stroje M lze vypozorovat,
jak funguje. Postupně vždy nahradí nejlevější znak a nebo b na pásce znakem
X a poté také nejpravější znak a nebo b znakem X. Toto se opakuje, dokud na pásce
zbývají znaky a nebo b.
Stroj M akceptuje, pokud poslední znak nahrazený za X byl a, nebo pokud po nahrazení
nejpravějšího znaku ve slově nezbyly žádné znaky a a b. Z toho se dá odvodit, že
Turingův stroj M rozhoduje jazyk všech slov, která mají sudou délku, nebo je jejich
prostřední symbol a. Jinými slovy
L(M) = ({a, b}2
)∗
∪ {wav | |w| = |v|}.
Tedy jedno ze slov délky alespoň 3, které stroj M neakceptuje, je aba. Vypočet nad
tímto slovem je:
(q0, aba ω
, 0) (q0, aba ω
, 1) (qA, Xba ω
, 2)
(q, Xba ω
, 3) (q, Xba ω
, 4)
(qr, Xba ω
, 3) (qback , XbX ω
, 2)
(qback , XbX ω
, 1) (q0, XbX ω
, 2)
(q, XXX ω
, 3) (qr, XXX ω
, 2)
(qreject , XXX ω
, 1)