Zásobníkové automaty

Automaty, ktoré pracujú s bezkontextovou gramatikou.

Bezkontextová gramatika

Je taká gramatika, kde pravidlá majú tvar: $A \to α$ , pričom $A \in N$ (na ľavej strane je práve jeden neterminálny symbol); $α \in (N \cup T)^{+}$ (na pravej strane je ľubovoľná neprázdna postupnosť neterminálnych alebo terminálnych symbolov).

Zásobníkový automat

Zásobník

Je to pamäť typu LIFO (last in: first out), kde prvok vložený ako posledný ide von prvý.

Zásobníkové automaty definujeme ako sedmicu:

$A = (K, Σ, Γ, δ, q_{0} Z_{0}, F)$

$A$ - označenie automatu;
$K$ - konečná, neprázdna množina neterminálnych symbolov;
$Σ$ - konečná, neprázdna množina terminálnych symbolov (znakov, ktoré automat rozpoznáva);
$Γ$ (gamma) - zásobníková abeceda (symboly, ktoré sa môžu nachádzať v zásobníku);
$δ$ - prechodové funkcie (napr.: orientovaný, ohodnotený multigraf - vizuálna reprezentácia automatu);
$q_{0}$ - začiatočný prechod (musí patriť do množiny $K$ );
$Z_{0}$ - začiatočný zásobníkový symbol (ktorý symbol je v zásobníku ako prvý?);
$F$ - množina konečných neterminálnych symbolov (stavov)

Zásobníkové automaty fungujú tak, že pri každom prechode (kroku výpočtu) môžeme prepísať posledný symbol v zásobníku na iný symbol, alebo postupnosť symbolov. Prechody obsahujú rôzne podmienky, teda môžeme vytvoriť algoritmy, ktoré prejdú po určitých prechodoch ak sa na vrchu zásobníka nachádza určitý symbol.

Podľa toho, či je množina stavov $F$ prázdna ( $F = \emptyset$ ), rozlišujeme dva typy automatov:

Automaty, ktoré rozpoznávajú koncovým stavom;
- Dôležité je, či výpočet určitého slova skončí v koncovom stave, pričom neberieme do úvahy to, aké symboly sa nachádzajú v zásobníku.
Automaty, ktoré rozpoznávajú prázdnou pamäťou;
- Pri tomto spôsobe rozpoznávania musí byť prázdna pamäť (zásobník) pre to, aby slovo patrilo do daného jazyka.

Ak sa na automat pozrieme, vieme určiť spôsob rozpoznávania: ak obsahuje koncový stav, tak rozpoznáva koncovým stavom (teda, vidíme v zápise definovanú množinu $F$ , alebo jednoducho v obrázku vidíme stav ktorý je označený ako koncový - je označený dvojitým kruhom). Tým pádom vieme aj určiť podmienku, ktorá je nutná pre to aby slovo patrilo do daného jazyka.

Ku každej bezkontextovej gramatike existuje zásobníkový automat. Tento prevod sa dá urobiť tiež naopak, ale je to ťažšie zrealizovať.

Úloha na zásobníkový automat

Povedzme, že máme zadaný graf automatu (teda, poznáme $δ$ ) a musíme tento automat vedieť popísať (teda, definovať $A$ ) a určiť, aké slová rozpoznáva a akým spôsobom.

{{#display_diagram:Drawio:Príklad zásobníkového automatu}}Povedzme, že máme zadané slovo $w = a a b b a a b b$ , a máme na tomto slove zrealizovať výpočet a na základe toho určiť, čo daný automat robí.

Ak sa pozrieme na automat, vidíme že prechody obsahujú tri časti oddelené bodkočiarkou (;):

Symbol, ktorý je na vstupe (túto časť prechodu už poznáme z automatov bez zásobníka);
Symbol, ktorý sa nachádza na vrchu zásobníka - tento prechod môžeme použiť iba vtedy, ak sa tento symbol nachádza na vrchu zásobníka
Symbol, ktorý sa má nahradiť na mieste posledného symbola v zásobníku - ak zrealizujeme tento prechod, nahradíme posledný symbol v zásobníku týmto symbolom (alebo viacerými symbolmi: napr. ak chceme pridať symbol, tak v podstate posledný symbol nahradíme rovnakým symbolom za ktorým bude nasledovať symbol ktorý chceme pridať - preto nehovoríme, že symboly môžeme pridávať, v podstate vždy iba symboly nahradzujeme).

Z týchto symbolov vieme určiť:

$K = {q_{0}, q_{F}}$ - množina neterminálnych symbolov predstavuje všetky vrcholy v grafe (v podstate iba vypíšeme všetky symboly v kruhoch);
$Σ = {a, b}$ - množina terminálnych symbolov obsahuje všetky symboly, ktoré sú v prechodoch na prvom mieste;
$Γ = {Z_{0}, a, b}$ - množina zásobníkových symbolov obsahuje všetky symboly, ktoré sú v prechodoch na druhom mieste;
F={qF} - množina koncových stavov, v tomto prípade je tam práve jeden dvojitý kruh, a to qF.
- Ak vieme, že do množiny $F$ patrí práve jeden neterminálny symbol, vieme povedať že automat rozpoznáva koncovým stavom. Ak výpočet skončí v tomto stave, slovo je automatom akceptované a patrí do daného jazyka;
Výpočet začína v stave $q_{0}$ , začiatočný symbol v zásobníku je (podľa konvencie) $Z_{0}$ ;

Z informácií vyššie vieme vytvoriť definíciu automatu (a áno, musí to byť presne v takomto poradí):

$A = (K, Σ, Γ, δ, q_{0}, Z_{0}, F)$

Výpočet slova: $(q_{0}; a a b b a b; Z_{0}) ⊢ (q_{0}; a b b a b; a Z_{0}) ⊢ (q_{0}; b b a b; a a Z_{0}) ⊢ (q_{0}; b a b; a Z_{0}) ⊢ (q_{0}; a b; Z_{0}) ⊢ (q_{0}; a b; Z_{0}) ⊢ (q_{0}; b; a Z_{0}) ⊢ (q_{0}; ϵ; Z_{0}) ⊢ (q_{F}; ϵ; Z_{0})$

« Formálne automaty (konečné)

Syntaktická analýza v zásobníkových automatoch »