IB102 – úkol 9, příklad 1 – řešení Odevzdání: 1. 12. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Sestrojte deterministický úplný jednopáskový Turingův stroj rozhodující
jazyk L. Princip práce vašeho Turingova stroje popište slovně a poté stroj zadefinujte i
formálně.
L = {an
bk
| n ≥ 0, k > 0, n je dělitelné k}
Na intuitivní úrovni bude hledaný Turingův stroj pracovat tak, že pro vstupní slovo ve
tvaru an
bk
pro n ≥ 0, k > 0 na pásce bude opakovaně přepisovat k výskytů znaku a znaky
A. Pokud po nějakém z těchto kroků zůstane na pásce méně než k znaků a, není vstupní
slovo v jazyce L, protože n není dělitelné k. Pokud po nějakém z těchto kroků naopak na
pásce nezůstane žádné písmeno a, slovo do jazyka L patří, protože n je dělitelné k.
Hledaný Turingův stroj rozhodující jazyk L bude pracovat v několika krocích:
1. Rozhodni, jestli vstupní slovo patří do jazyka {b}+
, {a}+
{b}+
, nebo ani do jednoho
z nich. Pokud patří do jazyka {b}+
, akceptuj, protože 0 je dělitelná libovolným kladným
číslem. Pokud patří do jazyka {a}+
{b}+
, přesuň se na konec pásky a pokračuj
krokem 2. Pokud nepatří ani do jednoho z nich, zamítni.
2. Jsou-li na pásce jen symboly A a B, akceptuj. Jinak zkus na pásce najít nejpravější
výskyt znaku b. Pokud na pásce žádné písmeno b není, pokračuj krokem 4. Pokud
ano, přepiš ho na B a pokračuj krokem 3.
3. Zkus na pásce najít nejpravější výskyt znaku a. Pokud na pásce žádné písmeno a
není, zamítni. Pokud ano, přepiš ho na A a vrať se na krok 2.
4. Přepiš všechny znaky B na b, vrať se na pravý konec pásky a pokračuj krokem 2.
Poznámka. Korektnost tohoto algoritmu vyplývá z toho, že pro obsah pásky y ω
vždy
platí n = #A(y) + #a(y) ∧ k = #B(y) + #b(y) a při každém vstupu do kroku 2 platí
invariant #A(y) mod k = #B(y) mod k.
Formálně se jedná o Turingův stroj M = (Q, Σ, Γ, , δ, , q0, qacc, qrej), kde
Q = {q0, qa, qb, qcheckB, qret, qmarkA, qmarkB, qclearA, qacc, qrej},
Σ = {a, b},
Γ = { , a, b, A, B, }
a přechodová funkce δ je určena následující tabulkou1
:
1
Držíme se konvence ze skript, kde symbol „−“ v tabulce vyjadřuje, že není podstatné, co se zapíše
na uvedené místo (může to být cokoli vyhovující definici).
IB102 – úkol 9, příklad 1 – řešení Odevzdání: 1. 12. 2014
Vypracoval(a): UČO:
Skupina:
a b A B
q0 (q0, , R) (qa, a, R) (qcheckB, b, R) − − (qrej, −, −)
qa − (qa, a, R) (qb, b, R) − − (qrej, −, −)
qb − (qrej, −, −) (qb, b, R) − − (qmarkB, , L)
qcheckB − (qrej, −, −) (qcheckB, b, R) − − (qacc, −, −)
qmarkB (qacc, −, −) (qclearB, a, R) (qmarkA, B, L) (qmarkB, A, L) (qmarkB, B, L) −
qmarkA (qrej, −, −) (qret, A, R) (qmarkA, b, L) (qmarkA, A, L) (qmarkA, B, L) −
qret − (qret, a, R) (qret, b, R) (qret, A, R) (qret, B, R) (qmarkB, , L)
qclearB − − − (qclearB, A, R) (qclearB, b, R) (qmarkB, , L)
Ve výše uvedeném popisu odpovídají stavy q0, qa, qb a qcheckB kroku 1, stav qmarkB kroku
2, stav qmarkA kroku 3 a stav qclearB kroku 4. Stav qcheckB slouží na kontrolu, jestli slovo
patří do jazyka {b}+
. Stav qret slouží na přesun čtecí hlavy na pravý konec pásky.