IB102 – úkol 9, příklad 1 – řešení Odevzdání: 2. 12. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme následující jazyk nad abecedou Σ = {a}:
L = {a(3n)
| n ≥ 0}
Sestrojte deterministický úplný jednopáskový Turingův stroj rozhodující jazyk L. Intuitivní
princip práce stroje popište slovně a poté stroj zadefinujte i formálně.
Řešením je například Turigův stroj T zadefinovaný níže (přechodová funkce δ je pro
přehlednost zadána tabulkou).
T = (Q, Σ, Γ, , , δ, q0, qacc, qrej)
Σ = {a}
Γ = { , , a, #}
Q = {q0, q1, qacc, qrej, qa, qaa, qaaa, qr}
δ a #
q0 (q0, , R) (qrej, , R) (q1, #, R) (q0, #, R)
q1 (q0, , R) (qacc, , R) (qaa, #, R) (q1, #, R)
qa (q0, , R) (qrej, , R) (qaa, #, R) (qa, #, R)
qaa (q0, , R) (qrej, , R) (qaaa, a, R) (qaa, #, R)
qaaa (q0, , R) (qr, , L) (qa, #, R) (qaaa, #, R)
qr (q0, , R) (qr, , L) (qr, a, L) (qr, #, L)
Hlavní myšlenka: Číslo je mocninou tří, právě když je to 1, nebo je dělitelné třemi a
po vydělení dostaneme nějakou jinou mocninu tří. Stroj T bude tuto vlastnost ověřovat
tak, že bude počet znaků a na pásce postupně dělit třemi.
Neformální popis stroje: Stroj projde celou pásku až po první výskyt znaku . Jestli
nenajde žádný znak a, slovo zamítne. Jestli najde právě jeden, slovo akceptuje. Jestli
najde víc, dvě třetiny z nich nahradí znakem # (tímhle způsobem třikrát zmenšíme počet
znaků a). Pokud „dělení“ nevyjde beze zbytku, stroj slovo zamítne, jinak proces opakuje
od začátku. Při průchodu páskou počítáme jenom znaky a (znaky # se ignorují, hlava se
pouze posune).
Jednotlivé stavy vyjádřují následující:
• q0 indikuje, že v průchodu doposud nebyl žádný znak a;
• q1 indikuje, že v průchodu bylo doposud jen jedno a (což znamená, že lze akceptovat);
• qa, qaa, qaaa indikují, že dosavadní počet a modulo 3 je rovný 1, 2, resp. 0 (a celkový
počet a je větší než jedna);
• qr slouží ke zpětnému chodu (obsah pásky se nemodifikuje).
1