Deterministic pushdown automata and deterministic context-free languages

A deterministic pushdown automaton (DPDA) is a PDA $M=(Q,\mathrm{\Sigma }\cup \{⊣\},\mathrm{\Gamma },\delta ,q_0,Z_0,F)$ with a distinguished endmarker $⊣\mathrm{\notin }\mathrm{\Sigma }$ such that:

• for each state $q$, stack symbol $Z$, and $a\in \mathrm{\Sigma }\cup \{⊣,\epsilon \}$, at most one pair $(p,\beta )$ lies in $\delta (q,a,Z)$;
• if some $\epsilon$-move is enabled from $(q,Z)$, then no input-reading move is enabled from that same pair $(q,Z)$.

The machine recognizes a language $L\subseteq {\mathrm{\Sigma }}^{\ast }$ by final state when it accepts exactly the marked inputs $w⊣$ in the sense of Acceptance by final state for a PDA.

A language is deterministic context-free when some DPDA recognizes it.

• The endmarker is not part of the language alphabet. It is an auxiliary symbol used to force the machine to detect the end of the real input.

• Determinism forbids branching on an input symbol or on $\epsilon$, as well as the simultaneous availability of an $\epsilon$-move and an input-reading move from the same state/top-of-stack pair.