IB102 – úkol 8, příklad 1 – řešení Odevzdání: 25. 11. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme následující jazyk nad abecedou Σ = {a, b, c}:
L = {wcn
| w ∈ {a, b}∗
∧ #a(w) + (#b(w) mod 3) = n, n ≥ 0}
Sestrojte zásobníkový automat akceptující jazyk L. Jasně uveďte, jakým způsobem
váš automat akceptuje (koncovým stavem, prázdným zásobníkem).
Budeme sestavovat zásobníkový automat akceptující koncovým stavem.
Idea za volbou stavů a zásobníkové abecedy: pro rozpoznání tohoto jazyka si potřebujeme
zapamatovat dva údaje – počet znaků a v podslově w a počet znaků b mod 3
v podslově w. Jelikož první z těchto hodnot může být libovolná (není shora omezená),
musíme si ji pamatovat v zásobníku. Naopak, počet b mod 3 je jen konečná informace a
proto si ji stačí pamatovat ve stavové jednotce.
Kromě toho si ještě musíme ve stavové jednotce držet informaci, zda jsme v podslově
w nebo již čteme cčka.
Množina stavů bude:
Q = {qε, q0, q1, q2, p0, p1, r}
Jejich význam je následující: Stavy q0, q1, q2 používáme, dokud se nacházíme v podslově
w, počítáme pomocí nich #b(w) mod 3.
Stav qε slouží jen jako iniciální a k umožnění akceptace prázdného slova, tedy bude
akceptující.
Stavy p0 a p1 indikují počet b mod 3, který dosud nebyl vyrovnán cčky, používají se
v podslově cn
. Stav r slouží pouze k akceptování.
Při kontrole počtu cček budeme nejprve vyrovnávat počet b mod 3 (tedy budeme konzumovat
#b(w) mod 3 cček ze vstupu) teprve potom budeme vyrovnávat počet aček (tedy
konzumovat #a(w) cček ze vstupu).
Na zásobníku potřebujeme udržovat jen počet aček, stačí nám tedy dva zásobníkové
symboly, z čehož jeden je počáteční.
Γ = {⊥, A }
Nyní můžeme přistoupit k sestrojení samotného zásobníkového automatu A:
A = (Q, Σ, Γ, δ, qε, ⊥, {qε, r})
Přechodovou funkci popíšeme ve dvou částech, první se týká zpracovávání podslova w:
δ(qε, a, ⊥) = {(q0, A⊥)}
δ(qε, b, ⊥) = {(q1, ⊥)}
∀X ∈ Γ. δ(q0, a, X) = {(q0, AX)}
∀X ∈ Γ. δ(q0, b, X) = {(q1, X)}
∀X ∈ Γ. δ(q1, a, X) = {(q1, AX)}
∀X ∈ Γ. δ(q1, b, X) = {(q2, X)}
∀X ∈ Γ. δ(q2, a, X) = {(q2, AX)}
∀X ∈ Γ. δ(q2, b, X) = {(q0, X)}
1
IB102 – úkol 8, příklad 1 – řešení Odevzdání: 25. 11. 2013
Vypracoval(a): UČO:
Skupina:
Stav qε opustíme jakmile přečteme první písmeno vstupu (které musí být a, nebo b –
jinak by slovo nepatřilo do jazyka).
Pokud je na vstupu a, chovají se všechny qi-stavy stejně – nezávisle na vrcholu zásobníku
nad něj přidají symbol A. Naopak, pokud je na vstupu b, zůstává zásobník nezměněn
a stavová jednotka přechází do dalšího qi-stavu.
Následující stavy zajišťují kontrolu počtu cček, tedy pracují v podslově cn
:
δ(q0, ε, ⊥) = {(r, ε)}
δ(q0, c, A) = {(p0, ε)}
∀X ∈ Γ. δ(q1, c, X) = {(p0, X)}
∀X ∈ Γ. δ(q2, c, X) = {(p1, X)}
∀X ∈ Γ. δ(p1, c, X) = {(p0, X)}
δ(p0, c, A) = {(p0, ε)}
δ(p0, ε, ⊥) = {(r, ε)}
Tato kontrola probíhá tak, že se nejprve zkonzumují ze vstupu cčka na vyrovnání počtu
b mod 3 a potom (ve stavu p0) se kontroluje, jestli zbývající počet cček souhlasí s počtem
A na zásobníku.
Musíme však dávat pozor na to, že pokud ve slově w nebyla žádná ačka, a zároveň
byl počet b násobkem 3, pak očekáváme 0 cček a tedy musíme umožnit ε-přechod do
akceptujícího stavu.
Pokud jsme došli na vyrovnaný stav (tedy dosud zkonzumované slovo náleží do L, na
vrcholu zásobníku je dno ⊥), přejdeme do akceptujícího stavu. Ten již žádné přechody
nemá, aby nemohl akceptovat v případě, že by ještě následovala další písmena na vstupu.
2