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 a musíme ho vedieť popísať (teda, definovať $A$ ) a určiť, aké slová rozpoznáva a akým spôsobom.

« Formálne automaty (konečné)

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