Deterministic pushdown automaton

A (not necessarily deterministic) PDA ${\displaystyle M}$ can be defined as a 7-tuple:

${\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)}$

where

• ${\displaystyle Q\,}$ is a finite set of states
• ${\displaystyle \Sigma \,}$ is a finite set of input symbols
• ${\displaystyle \Gamma \,}$ is a finite set of stack symbols
• ${\displaystyle q_{0}\,\in Q\,}$ is the start state
• ${\displaystyle Z_{0}\,\in \Gamma \,}$ is the starting stack symbol
• ${\displaystyle A\,\subseteq Q\,}$, where ${\displaystyle A}$ is the set of accepting states
• ${\displaystyle \delta \,}$ is a transition function, where

${\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$

where ${\displaystyle *}$ is the Kleene star, meaning that ${\displaystyle \Gamma ^{*}}$ is "the set of all finite strings (including the empty string ${\displaystyle \varepsilon }$) of elements of ${\displaystyle \Gamma }$", ${\displaystyle \varepsilon }$ denotes the empty string, and ${\displaystyle {\mathcal {P}}(X)}$ is the power set of a set ${\displaystyle X}$.

M is deterministic if it satisfies both the following conditions:

• For any ${\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }$, the set ${\displaystyle \delta (q,a,x)\,}$ has at most one element.
• For any ${\displaystyle q\in Q,x\in \Gamma }$, if ${\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}$, then ${\displaystyle \delta \left(q,a,x\right)=\emptyset }$ for every ${\displaystyle a\in \Sigma .}$

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are those languages that are accepted by final state and are prefix-free: no word in the language is the prefix of another word in the language.

The usual acceptance criterion is final state, and it is this acceptance criterion which is used to define the deterministic context-free languages.

If ${\displaystyle L(A)}$ is a language accepted by a PDA ${\displaystyle A}$, it can also be accepted by a DPDA if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to ${\displaystyle L(A)}$. If ${\displaystyle L(A)}$ can be accepted by a PDA it is a context free language and if it can be accepted by a DPDA it is a deterministic context-free language (DCFL).

Not all context-free languages are deterministic. This makes the DPDA a strictly weaker device than the PDA. For example, the language L_p of even-length palindromes on the alphabet of 0 and 1 has the context-free grammar S → 0S0 | 1S1 | ε. If a DPDA for this language exists, and it sees a string 0ⁿ, it must use its stack to memoize the length n, in order to be able to distinguish its possible continuations 0ⁿ 11 0ⁿ ∈ L_p and 0ⁿ 11 0ⁿ⁺² ∉ L_p. Hence, after reading 0ⁿ 11 0ⁿ, comparing the post-"11" length to the pre-"11" length will make the stack empty again. For this reason, the strings 0ⁿ 11 0ⁿ 0ⁿ 11 0ⁿ ∈ L_p and 0ⁿ 11 0ⁿ 0ⁿ⁺² 11 0ⁿ⁺² ∉ L_p cannot be distinguished.[2]

Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages,[3] which is a proper subclass of the DCFL.[4] In the case of a PDA, this restriction has no effect on the class of languages accepted.

• Hamburger, Henry; Dana Richards (2002). Logic and Language Models for Computer Science. Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331. ISBN 0-13-065487-6.CS1 maint: location (link)