Deterministyczny automat ze stosem

Deterministyczny automat ze stosem (DPDA, ang. deterministic pushdown automaton) – automat ze stosem, którego funkcja przejść spełnia dodatkowy warunek:

• Dla każdego ${\displaystyle q\in Q,a\in \Sigma ,x\in \Phi ,}$ mamy ${\displaystyle \sharp \delta (q,a,x)\leqslant 1.}$
• Dla każdego ${\displaystyle q\in Q,x\in \Phi ,}$ jeśli ${\displaystyle \delta (q,\epsilon ,x)\neq \emptyset ,}$ to dla każdego ${\displaystyle a\in \Sigma }$ zachodzi ${\displaystyle \delta (q,a,x)=\emptyset .}$

Innymi słowy, deterministyczny automat ze stosem ma możliwość co najwyżej jednego przejścia z dowolnej konfiguracji ${\displaystyle (q,a,x)\in Q\times (\Sigma \cup \left\{\epsilon \right\})\times \Phi }$ oraz jeżeli jest określone przejście dla pewnego stanu i symbolu na stosie pod wpływem słowa pustego ${\displaystyle \epsilon ,}$ to wówczas jest ono jedynym możliwym przejściem dla tego układu w tym automacie.