Zásobníkové automaty
Podobně jako slouží konečný automat k rozpoznávání regulárních výrazu, slouží zásobníkový automat k rozpoznání bezkontextových jazyků. Konečný automat si pamatuje akorát aktuální stav. Neví kolik znaku přečetl a které to byly. A to právě potřebujeme k rozpoznání bezkontextového jazyku. Zásobníkový automat je v podstatě konečný automat rozšířený o zásobník.
Zásobníkový automat na základě aktuálního znaku na vstupu, prvního (posledně zapsaného) znaku v zásobníku a aktuálního stavu, změní svůj stav a přepíše znak v zásobníku, a to podle daného pravidla δ.
| pravidlo | vysvětlení |
|---|---|
| δ(S,a,Z)={(S,AZ)} |
přidání prvku do zásobníku Do zásobníku se přidá A. |
| δ(S,a,Z)={(S,A)} |
přepsání prvku v zásobníku První prvek zásobníku se přepíše na A. |
| δ(S,a,Z)={(S, ε)} |
smazání prvku v zásobníku První prvek zásobníku se smaže (nahradí prázdným slovem ε) |
| δ(S,a,Z)={(T, Z)} |
změna stavu Stav S se změní na stav T. Pro stav T budou platit pravidla typu δ(T,... |
| δ(S,a,Z)= ∅ |
pád automatu Ukončení výpočtu, slovo nebylo přijato. |
Kdyby bylo pravidlo z obrázku definováno takto δ(S,a,Z)={(U,AZ)}, změnil by se stav S na stav U a zásobník by obsahoval znaky AZ. V dalším kroku by se na zásobníku četlo A a na vstupu další znak slova, což je 'a'. Aplikovalo by se tedy pravidlo δ(U,a,A).
Pravidla definují chování automatu. V následující tabulce jsou popsány různé typy pravide. Všechny se aplikují v situaci, která je zobrazena na obrázku a popsána v odstavci výše.
Definice zásobníkového automatu 
:
Zásobníkový automat M je definován jako šestice M = (Q,Σ, Γ, δ, q0, Z0), kde
• Q je konečná neprázdná množina stavů,
• Σ je konečná neprázdná množina vstupních symbolů (vstupní abeceda),
• Γ je konečná neprázdná množina zásobníkových symbolů (zásobníková abeceda),
• q0 ∈ Q je počáteční stav,
• Z0 ∈ Γ je počáteční zásobníkový symbol a
• δ je zobrazení množiny Q×(Σ∪{ε})×Γ do množiny všech konečných podmnožin množiny Q × Γ∗.