Deterministic Pushdown Automata (DPDA): Definition and an Example

A deterministic pushdown automaton (DPDA) is a pushdown automaton where the computation is deterministic: for any configuration, there is at most one applicable transition. Like all pushdown automata, a DPDA has a finite control plus a stack (unbounded memory) that it can push to and pop from while reading the input.

Formally, many textbooks define a (possibly nondeterministic) pushdown automaton as a 7-tuple, typically of the form $(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, and a DPDA is one where the transition relation $\delta$ is restricted so that it behaves like a partial function (not a relation).

Key idea: DPDA determinism couples (i) the current state, (ii) the next input symbol (or an $\varepsilon$-move), and (iii) the current top-of-stack symbol into a unique next move. This prevents the machine from “guessing” how to continue.

Mermaid sketch of the DPDA components:

Footnotes

1. Deterministic pushdown automaton / pushdown automaton formalism - Overview and formal definitions of PDAs and determinism ideas. ↩

Formal definition (typical DPDA template)

A common formalization uses a transition function
$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to Q \times \Gamma^{*}$
for a DPDA, meaning the machine reads either a real input symbol or takes an $\varepsilon$-transition, and in either case it updates the stack by replacing the top symbol with a (possibly longer) string. This captures the “partial function” nature of determinism.

Determinism is sometimes stated as a restriction on a nondeterministic transition relation (e.g., “for any $(q,a,X)$ there is at most one possible $(q',\gamma)$”). The operational intuition is the same: from any configuration, the next configuration is uniquely determined.

Important concepts (terms used below):

• Pushdown automaton
• Stack configuration
• Transition function
• Epsilon transition

Footnotes

1. Pushdown automaton: transition function and $\u03b5$-moves - Details on transitions and the role of $\u03b5$-moves in PDA definitions. ↩

2. Deterministic pushdown automaton / pushdown automaton formalism - Overview and formal definitions of PDAs and determinism ideas. ↩

Language-recognition power (high-level context)

DPDAs are still more powerful than DFAs/NPAs because stacks add memory. In particular, deterministic and nondeterministic pushdown automata do not recognize exactly the same family of languages—there exist context-free languages not recognizable by any DPDA. This is typically discussed in the theory of context-free languages and DPDA vs. NPDA comparisons.

(For the purpose of this section, we focus on defining DPDA deterministically and constructing one for a standard example.)

Footnotes

1. Context-free languages and pushdown automata; relation to deterministic PDAs - Context-free languages and their correspondence with PDA capabilities. ↩

An example DPDA: recognizing L=\{a^n b^n : n\\ge 0\\}

Let $L = \\{a^n b^n : n\\ge 0\\}$ be the set of strings with equal numbers of $a$’s followed by $b$’s. The classic DPDA idea is:

1. While reading $a$’s, push one stack symbol per $a$.
2. When the input switches to $b$’s, pop one stack symbol per $b$.
3. Accept when the input is fully consumed and the stack is back to its bottom marker.

This yields determinism because at any point the next move is forced by:

• whether the next input symbol is $a$, $b$, or end-of-input, and
• what symbol is currently on top of the stack.

DPDA design

We choose:

• Input alphabet: $\Sigma = \\{a,b\\}$
• Stack alphabet: $\Gamma = \\{Z_0, A\\}$ where $Z_0$ is bottom-of-stack marker and $A$ counts $a$’s.
• States: $Q = \\{q_{start}, q_{pop}, q_{acc}\\}$
• Start state: $q_{start}$
• Initial stack symbol: $Z_0$
• Accepting state(s): $F = \\{q_{acc}\\}$

A transition set (function-style) is described as follows (using the “replace top symbol with a string” convention for stack updates). This is a standard DPDA construction pattern for $a^n b^n$.

Transition behavior (informal)

• In state $q_{start}$:
  • On input $a$ with top $Z_0$ or $A$, push another $A$.
  • On input $b$ with top $A$, pop one $A$ and move to $q_{pop}$.
  • If input is empty and top is $Z_0$, accept (this corresponds to $n=0$).
• In state $q_{pop}$:
  • On input $b$ with top $A$, pop one $A$.
  • When input is empty and top is $Z_0$, accept.
  • Any attempt to read an $a$ after starting to pop is rejected (no transition).

Key DPDA determinism intuition

At any configuration:

• If you see an $a$ while still in the “push” phase, the only possible action is “push $A$”.
• If you see a $b$ in the “push” phase and top is $A$, the only possible action is “pop $A$ and switch phase”.
• If you see a $b$ in the “pop” phase and top is $A$, you must keep popping.
• If you see the wrong symbol for the phase (e.g., an $a$ while popping), there is no valid transition.

Footnotes

1. Deterministic pushdown automaton / pushdown automaton formalism - Overview and formal definitions of PDAs and determinism ideas. ↩

Execution trace table (compact)