An Introduction to Formal Languages and Automata, 7th Edition

7.3 DETERMINISTIC PUSHDOWN AUTOMATA AND DETERMINISTIC CONTEXT-FREE LANGUAGES

A deterministic pushdown accepter (dpda) is a pushdown automaton that never has a choice in its move. This can be achieved by a modification of Definition 7.1.

DEFINITION 7.3

A pushdown automaton M = (Q,Σ, Γ, δ, q₀, z, F) is said to be deterministic if it is an automaton as defined in Definition 7.1, subject to the restrictions that, for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ,

1. δ(q, a, b) contains at most one element,
2. if δ(q, λ, b) is not empty, then δ(q, c, b) must be empty for every c ∈ Σ.

The first of these conditions simply requires that for any given input symbol and any stack top, at most one move can be made. The second condition is that when a λ-move is possible ...