Deterministic pushdown automata

In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.

Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton.

A (not necessarily deterministic) PDA M can be defined as a 7-tuple:

where

M is deterministic if it satisfies both the following conditions:

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.

...
Wikipedia