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 $q\in Q,a\in \mathrm{\Sigma },x\in \mathrm{\Phi },$ mamy $\mathrm{♯}\delta (q,a,x)⩽1.$
• Dla każdego $q\in Q,x\in \mathrm{\Phi },$ jeśli $\delta (q,ϵ,x)\ne \mathrm{\varnothing },$ to dla każdego $a\in \mathrm{\Sigma }$ zachodzi $\delta (q,a,x)=\mathrm{\varnothing }.$

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