Zásobníkový automat je rozšířený konečný automat, který má navíc zásobník. Pro každé vstupní písmeno se může zastavit a pracovat se zásobníkem a pak posouvat čtecí hlavici dál.
Zásobníkový automat je sedmice ⟨Q,Σ,G,δ,q0,Z0,F⟩:
Q – stavů
Σ - konečná vstupní abeceda
G - konečná abeceda zásobníku
δ - zobrazení z Q × (Σ ∪ 𝜀) × G* do Q × G*
q0 ∈ Q je počáteční stav
Z0 ∈ G je počáteční symbol v zásobníku
F ⊆ Q je množina koncových stavů
Konfigurace zásobníkového automatu
Trojice (q, w, α) z konečné množiny Q × (Σ ∪ 𝜀) × G*, kde
- q je okamžitý vnitřní stav
- w je dosud nezpracovaná část vstupního řetězce
- 𝛼 je obsah zásobníku
(q0, w) nazveme počáteční konfigurací
(q,ε), kde q ∈ F, nazveme koncovou konfigurací.
Přechod
Nechť ⊢R je relace nad 𝑄 × ∑* × 𝐺* taková, že (𝑞, 𝑤, 𝛼𝛽) ⊢R (𝑝,𝑤',𝛾𝛽) právě tehdy, když 𝑤=𝑎𝑤' a (𝑝,𝛾) ∈ 𝛿(𝑞,𝑎,𝛼) pro nějaké 𝑎 ∈ ∑ ∪ {𝜀}, 𝛼,𝛽,𝛾 ∈ 𝐺*. Prvek relace ⊢𝑅 nazveme přechodem
Přijímání jazyku
Jazyk definovaný (přijímaný) ZA 𝑅:
- Přechodem do koncového stavu 𝐿(𝑅) = 𝑤: 𝑤 ∈ ∑∗,∃𝛾 ∈ 𝐺∗,∃𝑞∈𝐹, 𝑞0,𝑤,𝑍0 ⊢𝑅∗ (𝑞,𝜀,𝛾)
- S prázdným zásobníkem 𝐿 𝑅 = 𝑤:𝑤∈∑∗, ∃𝑞∈𝑄, 𝑞0,𝑤,𝑍0 ⊢𝑅∗ (𝑞,𝜀,𝜀)
Zásobníkový překladový automat
Definice: Zásobníkový překladový automat je uspořádaná osmice 𝑍𝑃𝐴 = (𝑄,∑,𝐺,𝐷,𝛿,𝑞0,𝑍0,𝐹), kde:
Q - množina stavů
Σ - konečná vstupní abeceda
G - konečná neprázdná abeceda zásobníku
D je konečná množina výstupních symbolů
δ - zobrazení z Q × (Σ ∪ {𝜀}) × G* do Q × G* × D*
q0 ∈ Q je počáteční stav automatu
Z0 ∈ G je počáteční stav zásobníku
F ⊆ Q je množina koncových stavů
Bezkontextové jazyky
L = {anbn: n ≥ 0}
Zádrhelem proč, tohle není regulární gramatika je ten, že n může být neomezené, ale stavů v konečném automatu je je konečně mnoho. Zásobník je u bezkontextové gramatiky definován jako neomezeně velký.