Deterministic PDAs

In general terms, a deterministic PDA is one in which there is at most one possible transition from any state based on the current input.

Formally, a deterministic PDA is a PDA where:

• for every state $P$, input symbol $\hbox{\lq }{a}\hbox{'}$ and stack symbol $t$, there is at most one transition of the form $(P,a,t)\mapsto(Q,u)$ for any state $Q$ and stack symbol $u$.

Any context-free language that can be converted to a deterministic PDA is called a deterministic CFL.