Deterministic Pushdown Automata

The Deterministic Pushdown Automata is a variation of pushdown automata that accepts the deterministic context-free languages.

A language L(A) is accepted by a deterministic pushdown automata if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to L(A). It is not as powerful as non-deterministic finite automata. That's why it is less in use and used only where determinism is much easier to implement.

A PDA is said to be deterministic if its transition function δ(q,a,X) has at most one member for -

a ∈ Σ U {ε}

So, for a deterministic PDA, there is at most one transition possible in any combination of state, input symbol and stack top.

Formal Definition of Deterministic PDA

A Deterministic PDA is 5 tuple -

M = (Σ,Γ,Q,δ,q)

Σ - It is a finite set which does not contain a blank symbol,
Γ - a finite set of stack alphabet,
Q - set of states,
q - start state,
δ - a transition function, denoted as -

δ : Q × (Σ ∪ {□}) × Γ → Q × {N,R} × Γ^∗