Zásobníkové automaty – úvod
Již víme, že výpočetním strojem pro regulární jazyky jsou konečné automaty. V kapitolách 8, 9
jsme podrobně rozebrali bezkontextové gramatiky, které generují bezkontextové jazyky. Dosud
však nevíme, jaký výpočetní stroj této třídě jazyků přísluší. V následujících dvou kapitolách
tento „rest doženeme a povíme si o zásobníkových automatech, zkráceně PDA (z anglického
jazyka Push-Down Automata).
Princip fungování PDA
Zásobníkový automat si představte jako vylepšený konečný automat. Opět se zde setkáváme se
vstupní páskou, na kterou jsou před začátkem výpočtu zkopírovány všechny symboly slova,
u kterého chceme zjistit, zda jej automat akceptuje či ne. I konečně stavová řídící jednotka
je zachována, pamatuje si aktuální stav a její čtecí hlava ukazuje na právě čtený symbol na
vstupní pásce.
Navíc však PDA obsahuje tzv. zásobník, neboli pomocnou paměť, do které můžeme ukládat
symboly. Konečně stavová řídící jednotka se tedy rozhoduje o dalším kroku nejen na základě
symbolu na vstupní pásce a aktuálního stavu, ale také podle toho, co má na zásobníku. Prohlédněte
si obrázek 1 znázorňující strukturu zásobníkového automatu.
a c a a b c b b vstupní páska
konečně stavová
řídící jednotka
Z
c
A
a
A
zásobník
čtecí
hlava
1. Na vstupní pásku se zapíše slovo w u kterého zjišťujeme, zda jej PDA akceptuje. Slovo w
se na vstupní pásku zapíše zleva doprava. Na začátku výpočtu se čtecí hlava posune na
první symbol slova w.
2. Zásobník funguje na principu LIFO (Last in, first out) - poslední symbol, který přišel do
zásobníku, je odejde jako první.
3. Konečně stavová řídící jednotka „vidí pouze na vrchol zásobníku, tj. na symbol, který
byl do zásobníku naposledy zapsán.
4. Čtení symbolu z vrcholu zásobníku je destruktivní, tj. pokud přečteme symbol, tak jej
zároveň mažeme.
1
Definice – nedeterministický zásobníkový automat
Nedeterministický zásobníkový automat (PDA) je sedmice (Q, Σ, Γ, δ, q0, Z0, F) kde:
Q : konečná množina stavů
Σ : konečná množina vstupních symbolů
Γ : konečná množina zásobníkových symbolů,
δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ∗
) přechodová funkce
q0 ∈ Q : počáteční stav
Z0 ∈ Γ : počáteční symbol zásobníku
F ⊆ Q : podmnožina konečných stavů
Poznámka.
1. Všimněte si, že není dán vztah množin Σ, Γ. To znamená, vstupní symbol může být i
zásobníkovým symbolem, což se v praxi často stává.
2. Definičním oborem přechodové funkce δ je trojice (stav, vstupní symbol, zásobníkový symbol),
což odpovídá myšlence v úvodní části tohoto textu: konečně stavová řídící jednotka
se rozhoduje na základě aktuální stavu, symbolu na vstupní pásce a symbolu na vrcholu
zásobníku.
3. Oborem hodnot funkce δ je potenční množina P(Q × Γ∗
), tj. libovolný, ale konečný počet
uspořádaných dvojic (stav, řetězec symbolů). Konečně stavová řídící jednotka tedy
v každém kroku mění svůj stav a na vrchol zásobníku zapíše libovolnou posloupnost zásobníkových
symbolů.
Nyní si uvedeme formální definici toho, jak zásobníkový automat pracuje, tj. zavedeme pojmy
konfigurace, vnitřní konfigurace a krok výpočtu.
Definice – konfigurace, krok výpočtu
Buď M = (Q, Σ, Γ, δ, q0, Z0, F) nedeterministický zásobníkový automat.
1. Konfigurací rozumíme trojici (q, w, α), kde q ∈ Q je aktuální stav, w je dosud nepřečtená
část vstupního slova a α ∈ Γ∗
jsou všechny symboly zásobníku čtené zleva doprava.
2. Vnitřní konfigurací rozumíme libovolnou dvojici (q, α), kde význam obou složek je
stejný jako u konfigurace.
3. Krok výpočtu – tj. binární relaci → na množině konfigurací definujeme tak, že
(q, aw, Aα) → (p, w, βα),
právě když δ(q, a, A) obsahuje dvojici (p, β).
Popíšeme si jednotlivé symboly: q ∈ Σ ∪ {ε}, p, q ∈ Q, α, β ∈ Γ∗
, A ∈ Γ.
Poznámka.
Je zřejmé, že u binární relace → můžeme specifikovat její druh v závislosti na počtu kroků,
které při výpočtu udělá. Zápisem
• →k
(k ∈ N0) rozumíme výpočet přesně v k krocích.
2
• →∗
rozumíme výpočet v libovolně mnoha krocích (reflexivní a tranzitivní uzávěr →)
• →+
rozumíme výpočet v libovolném nenulovém počtu kroků (tranzitivní uzávěr →).
Nyní nám ještě zbývá uvést, za jakých podmínek PDA akceptuje vstupní slovo. Ještě než si
definici uvedeme, prozradíme, že přijímání slov je možné dvěma způsoby: koncovým stavem či
prázdným zásobníkem.
Definice – způsob akceptování PDA
Nedeterministický zásobníkový automat M = (Q, Σ, Γ, δ, q0, Z0, F) akceptuje
• koncovým stavem, právě když pro libovolné slovo w ∈ L(M) platí
(q0, w, Z0) →∗
(qaccept, ε, α),
kde qaccept ∈ F, α ∈ Γ∗
.
• prázdným zásobníkem, právě když pro libovolné slovo w ∈ L(M) platí
(q0, w, Z0) →∗
(q, ε, ε),
kde q ∈ Q.
Poznámka.
Způsob akceptování nejlépe rozpoznáte tak, že v případě PDA přijímajícího koncovým stavem
je množina F (tj. poslední položka sedmice) neprázdná. Naopak u PDA přijímajícího prázdným
zásobníkem je na posledním místě sedmice uvedena prázdná množina ∅.
Příklad 1.
Buď M = ({p, q, qaccept}, {a, b}, {B, Z}, δ, p, Z, qaccept) zásobníkový automat s funkcí δ:
δ(p, a, Z) = (p, BZ)
δ(p, a, B) = (p, BB)
δ(p, b, B) = (q, ε)
δ(q, b, B) = (q, ε)
δ(q, ε, Z) = (qaccept, Z)
Proveďte výpočet automatu M pro slova aabb, aab, baa, ab a rozhodněte, která z nich automat
M akceptuje a která ne.
Řešení.
1. (p, aabb, Z) → (p, abb, BZ) → (p, bb, BBZ) → (q, b, BZ) → (q, ε, Z) → (qaccept, ε, Z).
Slovo aabb ∈ L(M), protože jsme skončili v koncovém stavu a přečetli všechny symboly
ze vstupní pásky.
2. (p, aab, Z) → (p, ab, BZ) → (p, b, BBZ) → (q, ε, BZ). Slovo aab /∈ L(M), protože jsme
výpočet skončili v nekoncovém stavu q.
3. Pro počáteční konfiguraci (p, baa, Z) neexistuje přechod pomocí funkce δ, tedy bba /∈ L(M)
protože jsme jednak nepřečetli celé slovo a také neskončili v koncovém stavu.
4. (p, ab, Z) → (p, b, BZ) → (q, ε, Z) → (qaccept, ε, Z). Slovo ab ∈ L(M) – PDA přečetl celé
slovo a skončil výpočet ve stavu qaccept ∈ F.
3
Příklad 2.
Mějme PDA M = ({q0}, {a, b}, {A, B, Z}, δ, q0, Z, ∅) přijímající prázdným zásobníkem, kde přechodová
funkce δ je definována následovně:
δ(q0, a, Z) = (q0, AZ)
δ(q0, b, Z) = (q0, BZ)
δ(q0, a, A) = (q0, AA)
δ(q0, b, B) = (q0, BB)
δ(q0, a, B) = (q0, ε)
δ(q0, b, A) = (q0, ε)
δ(q0, ε, Z) = (q0, ε)
1. Proveďte výpočet na slovech abba, abbab, aabb, a, b, abab, baa.
2. Nalezněte jazyk L = L(M)
Řešení.
• (q0, abba, Z) → (q0, bba, AZ) → (q0, ba, Z) → (q0, a, BZ) → (q0, ε, Z) → (q0, ε, ε). Slovo
abba ∈ L(M), jelikož PDA přečetl celé slovo ze vstupní pásky a má prázdný zásobník.
• (q0, abbab, Z) → (q0, bbab, AZ) → (q0, bab, Z) → (q0, ab, BZ) → (q0, b, Z) → (q0, ε, BZ).
Slovo abbab bylo sice přečteno celé, zásobník však obsahuje řetězec BZ, tedy není prázdný.
Z toho důvodu abbab /∈ L(M).
• (q0, aabb, Z) → (q0, abb, AZ) → (q0, bb, AAZ) → (q0, b, AZ) → (q0, ε, Z) → (q0, ε, ε). Slovo
aabb ∈ L(M).
• (q0, a, Z) → (q0, ε, AZ) ⇒ a /∈ L(M).
• (q0, b, Z) → (q0, ε, BZ) ⇒ b /∈ L(M).
• (q0, abab, Z) → (q0, bab, AZ) → (q0, ab, Z) → (q0, b, AZ) → (q0, ε, Z) → (q0, ε, ε) ⇒
abab ∈ L(M)
• (q0, baa, Z) → (q0, aa, BZ) → (q0, a, Z) → (q0, ε, AZ) ⇒ baa /∈ L(M).
Pokud si vše dáme dohromady, zjistíme, že slova abba, aabb, abab ∈ L(M), kdežto abbab, a, b, baa /∈
L(M). PDA M funguje tak, že
• načítá-li symbol a ze vstupní pásky, pak v případě, že na vrcholu zásobníku jsou Z nebo
A, přidává na zásobník další symbol A. Pokud je však na vrcholu zásobníku B, tak jej
maže.
• V případě symbolu b je to opačně: je-li na vrcholu zásobníku B nebo Z, přidává další B,
pokud však na zásobníku „vidí A, maže jej.
Shrneme-li předchozí dva body, můžeme usoudit, že pomocí symbolů A si PDA pamatuje počet
a, pomocí B si zaznamenává počet b. Jakmile přečte celé slovo a na zásobníku má Z, znamená
to, že počet a byl stejný jako počet b. V tom případě vyprazdňuje zásobník a akceptuje dané
slovo. V opačném případě nedělá nic, čili nepřijímá slovo (nemá zásobník prázdný). PDA M
tedy přijímá jazyk
L(M) = {w ∈ {a, b}∗
| #a(w) = #b(w)}
4