Deterministické zásobníkové automaty

Řekneme, že PDA $M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ je deterministický, jestliže jsou splněny tyto podmínky:
1. Pro všechny $q \in Q, Z \in Γ$ platí: kdykoliv $δ (q, ϵ, Z) \neq = \emptyset$ , pak $δ (q, a, Z) = \emptyset$ pro všechna $a \in Σ$
2. Pro všechny $q \in Q, Z \in Γ$ a $a \in Σ \cup {ϵ}$ neobsahuje $δ (q, a, Z)$ více než jeden prvek
Podmínka 1 vylučuje možnost volby mezi krokem nezávislým na vstupním symbolu ( $ϵ$ -krokem) a krokem, kdy se ze vstupu čte.
Podmínka 2 říká, že je jak v případě čtecího kroku, tak i pro $ϵ$ -krok, neexistuje více než jedna varianta, jak dále pokračovat
Řekneme, že $L$ je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA $M$ takový, že $L = L (M)$

Normální forma (D)PDA

Řekneme, že DPDA $M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ je v normální formě jestliže platí:
- Je-li $δ (q, a, X) = (p, γ)$ , pak buď a. $γ = ϵ$ b. $γ = X$ c. $γ = Y X$ pro nějaké $Y \in Γ$ .
Identicky lze definovat normální formu i pro nedeterministický PDA. Uvedená normální forma tedy požaduje, aby jediné povolené operace nad zásobníkem byly
- odstranění vrcholového symbolu ze zásobníku podmínka (a) nebo
- přidání jednoho symbolu na vrchol zásobníku, podmínka (c),
- podmínka (b) povoluje změnit pouze vnitřní stav, a to bez změny zásobníku.