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 \Sigma ,x\in \Phi ,$ mamy $\sharp \delta (q,a,x)\leqslant 1.$
• Dla każdego $q\in Q,x\in \Phi ,$ jeśli $\delta (q,\epsilon ,x)\neq \emptyset ,$ to dla każdego $a\in \Sigma$ zachodzi $\delta (q,a,x)=\emptyset .$

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 (\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 $\epsilon ,$ to wówczas jest ono jedynym możliwym przejściem dla tego układu w tym automacie.