Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz:zasobnikove_automaty

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
  • FQ – 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})

  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, ε)}

Varianty ZA

Determinsitický zásobníkový automat

Deterministic pushdown automaton

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

  • qQ, aΣ ∪ {ε}, xΓ: |δ(q, a, x)| ≤ 1
    Existuje maximálně 1 přechod pro každou δ.
  • qQ, 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.

/var/www/wiki/data/pages/pitel/msz/zasobnikove_automaty.txt · Poslední úprava: 03. 07. 2012, 13.53:34 (upraveno mimo DokuWiki)