Zásobníkové automaty

Pushdown automaton

M = (Q, Σ, Γ, δ, q₀, Z₀, F)

Q – konečná množina stavů

Σ – konečná vstupní abeceda

Γ – konečná zásobníková abeceda

δ – přechodová funkce ve tvaru δ: Q × (Σ ∪ {ε}) × Γ → 2Q × Γ*

q₀ ∈ Q – počáteční stav

Z₀ ∈ Γ – počáteční symbol zásobníku

F ⊆ Q – množina koncových stavů

Jazyky přijímané ZA

Bezkontextové jazyky

Syntaktická analýza

Shora dolů

Top-down parsing

Přijímá prázdným zásobníkem!

P = ({q}, Σ, N ∪ Σ, δ, q, S, ∅)

Je-li A → α pravidlo z P, pak δ(q, ε, A) ∋ (q, α)

δ(q, a, a) = {(q, ε)} pro všechna a ∈ Σ

Zdola nahoru

Bottom-up parsing

Vyžaduje rozšířený zásobníkový automat!

P = ({q, r}, Σ, N ∪ Σ ∪ {#}, δ, q, #, {r})

Redukce: Je-li A → α pravidlo z P, pak δ(q, ε, α) ∋ (q, A)

Shift: δ(q, a, ε) = {(q, a)} pro všechna a ∈ Σ

Accept: δ(q, ε, S#) = {(r, ε)}

Varianty ZA

Determinsitický zásobníkový automat

Deterministic pushdown automaton

Automat je deterministický, pokud jsou splněný obě podmínky:

∀q ∈ Q, a ∈ Σ ∪ {ε}, x ∈ Γ: |δ(q, a, x)| ≤ 1
Existuje maximálně 1 přechod pro každou δ.

∀q ∈ Q, x ∈ Γ: pokud δ(q, ε, x) ≠ ∅, pak δ(q, a, x) = ∅ pro a ∈ Σ
Můžu mít přechod který nic nečte ze vstupu při daném vrcholu zásobníku, ale pak nesmím mít se stejným vrcholem zásobníku přechod který by něco četl. Proste to musí být jednoznačné!

Jiný zápis toho samého (je tam hezká symetrie):

∀a ∈ Σ: |δ(q, a, z)| ≤ 1 ∧ δ(q, ε, x) = ∅, nebo

∀a ∈ Σ: δ(q, a, z) = ∅ ∧ |δ(q, ε, x)| ≤ 1

Rozšířený zásobníkový automat

δ: Q × (Σ ∪ {ε}) × Γ* → 2Q × Γ*

Rozdíl je v Γ*, automat tedy může číst 0–n symbolů ze sásobníku.