Zásobníkové automaty

• PDA (push-down automat) si lze představit jako konečný automat s tím, že navíc obsahuje (pomocnou) paměť, která pracuje jako zásobník a jejíž velikost není shora omezená

Definice nedeterministického zásobníkového automatu

• Nedeterministický zásobníkový automat (PDA) je sedmice $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, kde:
  • $Q$ je konečná množina, jejíž prvky nazýváme stavy
  • $\Sigma$ je konečná množina, tzv. vstupní abeceda
  • $\Gamma$ je konečná množina, tzv. zásobníková abeceda
  • $\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to 2^{Q\times \Gamma }$ je přechodová funkce
    • Stavu, vstupnímu symbolu a symbolu na vrcholu zásobníku přiřadí množinu dvojic skládajících se ze stavu a řetězce zásobníkových symbolů
  • $q_0\in Q$ je počáteční stav
  • $Z_0\in \Gamma$ je počáteční symbol v zásobníku
  • $F\subseteq Q$ je množina koncových stavů

Konfigurace

• Nechť $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$ je PDA.

• Vnitřní konfigurací $M$ nazveme libovolný prvek $(q,\gamma )\in Q\times {\Gamma }^{\ast }$, kde $q$ je momentální stav PDA $M$ a $\gamma$ je celý obsah zásobníku s vrcholem psaným vlevo.

• Konfigurací nazveme libovolný prvek $(p,w,a)$ z $Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$, udávající mimo vnitřní konfigurace navíc i $w$ - dosud nepřečtenou část vstupního řetězu.

• Na množině všech konfigurací automatu $M$ definujeme binární relaci ${⊢}_M$, krok výpočtu takto: $(p,aw,Za){⊢}_M(q,w,\gamma a){\iff }^{def}\exists (q,\gamma )\in \delta (p,a,Z)\text{ pro }a\in \Sigma \cup \{ϵ\}$ Reflexivní a tranzitivní uzávěr relace kroku výpočtu značíme ${⊢}_M^{\ast }$

• Jazyk akceptovaný PDA $M$ koncovým stavem definujeme jako $L(M)=\{w\in {\Sigma }^{\ast }\mid (q_0,w,Z_0{⊢}^{\ast }(q_f,ϵ,a),\text{ kde }{q}_f\in F,a\in {\Gamma }^{\ast })\}$

• Jazyk akceptovaný PDA $M$ prázdným zásobníkem definujeme jako $L_e(M)=\{w\in {\Sigma }^{\ast }\mid (q_0,w,Z_0){⊢}^{\ast }(q,ϵ,ϵ),\text{ kde }q\in Q\}$

• Jazyk $L=L_e(M)$ pro nějaký PDA $M\iff L=L(N)$ pro nějaký PDA $N$

Navigace

Předchozí: Bezkontextové jazyky a jejich vlastnosti (uzávěrové vlastnosti, jednoznačnost) Následující: Deterministické zásobníkové automaty Celý okruh: 1. Teoretické základy informatiky