Deterministic PDAs and DCFLs

A deterministic pushdown automaton (DPDA) never has a choice of move: at most one transition applies for the current state, input symbol (or $\varepsilon$), and top-of-stack symbol, and $\varepsilon$-input moves cannot compete with a defined symbol move. Languages of DPDAs are deterministic context-free languages (DCFLs). Every DCFL is a CFL, but not conversely. Parsers for programming languages rely on deterministic stack discipline (LR parsing).

For every $q \in Q$, $a \in \Sigma$, $X \in \Gamma$:

So the machine has at most one legal action in every configuration. Condition 2 is the one that is easy to overlook: an $\varepsilon$-move and a symbol move on the same state and top symbol already make the PDA nondeterministic, even though each set has size 1.

DCFLs are usually defined via acceptance by final state. Acceptance by empty stack defines a strictly smaller family: a language is accepted by empty stack by some DPDA iff it is a DCFL with the prefix property (no string in the language is a proper prefix of another). Even the regular language $a^*$ fails it (a is a prefix of aa), so it has a DPDA by final state but none by empty stack.

The end-marker trick. For any $L$, the language $L\text{\textdollar} = \{ w\text{\textdollar} \mid w \in L \}$ (with a fresh symbol $\text{\textdollar}$) has the prefix property, because every string ends at its only $\text{\textdollar}$. And $L$ is a DCFL iff $L\text{\textdollar}$ is a DCFL. So "DCFL by final state" and "empty-stack DPDA for $L\text{\textdollar}$" describe the same family, and parsers add an end marker to the input for exactly this reason.

Proper inclusions:

Witnesses:

DCFLs are closed under complement but not union; CFLs are closed under union but not complement. A consequence: since DCFLs are closed under complement, a CFL whose complement is not a CFL cannot be a DCFL. For example $\overline{\{ww\}}$ is a CFL and its complement $\{ww\}$ is not, so $\overline{\{ww\}}$ is not a DCFL.

No guessing: while reading $a$, push; on first $b$, start popping; never return to pushing. Accept by final state when stack returns to bottom after the last $b$. Test that the stack has returned to its bottom and accept by final state only after the entire input is consumed; an explicit endmarker is an alternative convention.

A DPDA reading $a$'s then $b$'s must decide whether to match $a$'s against $b$'s or save the $b$'s to match $c$'s. Looking ahead cannot resolve both futures for all strings. Formal proofs use the DCFL pumping properties or known theorems; for classification, the witness language and this intuition are what you apply.

Simulation of a DPDA is deterministic:

Input positions are 0-based; i is the number of symbols already consumed.

Line 4 implements acceptance by final state: $w$ is accepted if any configuration reached after the whole input is read has an accepting state, including states passed during the trailing $\varepsilon$-moves. The last state alone is not the test. For example, take $\delta(q_0, a, Z_0) = (q_1, Z_0)$ and $\delta(q_1, \varepsilon, Z_0) = (q_2, Z_0)$ with $F = \{q_1\}$. On input a the run is $q_0, q_1, q_2$: it passes through accepting $q_1$ after reading all of a, so a is accepted although the run ends in $q_2 \notin F$. On $\varepsilon$ the run stays in $q_0$ and rejects; on aa it is stuck in $q_2$ with input left and rejects.

The simulator here supports machines with no infinite $\varepsilon$-move sequence; this is an input restriction, not a condition in the formal definition of a DPDA. For a fixed machine whose $\varepsilon$-bursts are uniformly bounded, the simulation time is $O(1+|w|)$. Merely excluding repeated finite control states without accounting for the stack does not prove such a bound.

If $x$ and $xy$ both empty the stack at their ends, the machine after $x$ already has empty stack and cannot read $y$. Hence no DCFL accepted by empty stack can contain both $x$ and $xy$ for $y\neq\varepsilon$.

Deterministic context-free languages are exactly the languages generated by LR($k$) grammars, and $k = 1$ already suffices for every DCFL. That theorem justifies why shift-reduce parsers can be built for typical programming languages. It also gives: every DCFL has an unambiguous grammar, so an inherently ambiguous language is never a DCFL. The converse fails: the even palindromes have the unambiguous grammar $S \to aSa \mid bSb \mid \varepsilon$ but are not a DCFL.

The intersection-emptiness row is the exception to note: two DCFLs can encode Post's correspondence problem, so even for DPDAs disjointness is undecidable.

DPDA as above. Sample: aabb accepts; aab rejects; aaabbb accepts.

$L_1 = \{a^n b^n \mid n \ge 0\}$ and $L_2 = \{a^n b^{2n} \mid n \ge 0\}$ are both DCFLs (push one or two symbols per $a$). Their union $L$ is a CFL (guess which branch) but not a DCFL. Proof idea: suppose a DPDA $M$ accepts $L$. Because $M$ is deterministic, its unique run on $a^n b^{2n}$ passes through the accepting configuration it reaches after $a^n b^n$. Build a PDA that runs $M$ and, from any accepting state reached after some $b$s, may switch to a copy of $M$ in which every $b$ is renamed $c$. It accepts $a^n b^n c^k$ ($k \ge 1$) iff $M$ accepts $a^n b^{n+k}$, that is iff $k = n$. So $\{a^n b^n c^n \mid n \ge 1\}$ would be context-free, which is false. Note that $\{a\} \cup \{a^n b^n \mid n \ge 1\}$ is a DCFL: the first $b$ (or the end of input) decides, so not every union fails.

Every regular language has a DFA; a DFA is a DPDA that ignores the stack. So $\mathrm{Regular} \subseteq \mathrm{DCFL}$.

Even-length palindromes over a 2-letter alphabet: CFL via nondeterministic midpoint guess; not DCFL.

Because a DPDA's run is unique, one can flip acceptance conditions to accept the complement, after two repairs: add a dead state so the machine never gets stuck before the input ends, and remove $\varepsilon$-loops so it never runs forever. A further subtlety is that one input string can pass through several states during $\varepsilon$-moves after its last symbol; the complement must accept iff none of those states is accepting. Nondeterministic PDAs cannot do this in general (CFLs are not closed under complement).

DPDA versus NPDA. Same hardware, different transition restraint; languages differ.

Common misconceptions.