DPDAs

Deterministic pushdown automata (DPDAs) are a restricted form of pushdown automata in which computation is deterministic. A DPDA is a seven-tuple (Q, Σ, Γ, δ, q0, Z0, F) where Q is a finite set of states, Σ is the input alphabet, Γ is the stack alphabet, Z0 is the initial stack symbol, and F is the set of accepting states. The transition function δ maps Q × (Σ ∪ {ε}) × Γ to Q × Γ*, and is constrained so that for every state q, stack symbol A, and input symbol a ∈ Σ ∪ {ε} there is at most one possible move. In addition, if δ(q, ε, A) is defined, then δ(q, a, A) is undefined for all a ≠ ε. This ensures a single computation path for any given input and configuration.

DPDAs recognize deterministic context-free languages (DCFLs). DCFLs are a proper subset of context-free languages; some CFLs are not deterministic. Canonical examples include the DCFL {a^n b^n | n ≥ 0}, which can be recognized by a DPDA, and languages like palindromes or certain copies of non-deterministic constructs that are not DCFLs.

Acceptance can be defined via final states or by emptying the stack. For DPDAs, these two acceptance modes yield the same class of languages, so a DPDA can be transformed between modes without leaving the DCFL class.

Key properties include that membership testing for DCFLs is decidable in linear time, and the emptiness problem for DPDAs is decidable. Equivalence of two DPDAs (whether they accept the same language) is undecidable. DCFLs are closed under complement and under intersection with regular languages, but not closed under union or intersection of two DCFLs.