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 × (Σ ∪ {ε}) × Γ → 2^{Q × Γ*}
• q₀ ∈ Q – počáteční stav
• Z₀ ∈ Γ – počáteční symbol zásobníku
• F ⊆ Q – množina koncových stavů

Bezkontextové jazyky

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 ∈ Σ

Bottom-up parsing

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

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

1. Redukce: Je-li A → α pravidlo z P, pak δ(q, ε, α) ∋ (q, A)
2. Shift: δ(q, a, ε) = {(q, a)} pro všechna a ∈ Σ
3. Accept: δ(q, ε, S#) = {(r, ε)}

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

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

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