Deterministic Pushdown Accepters
A deterministic pushdown accepter (DPDA) is a pushdown accepter M=(Q,S,U,P,qI,F) with a single initial state qI, and a program in which no more than one instruction is applicable in a given configuration.
A string w is accepted by a deterministic pushdown accepter M, if M has a move sequence (q,l ,l )Þ (q',w ,s ) where q' is a final state of M and s Î U*. The language recognized by M is the set of strings accepted by M.
A context-free language is called deterministic if it is recognized by some deterministic pushdown accepter.
The deterministic context-free languages are a proper subclass of all context-free languages. In particular, the language
Lnd={akbm| m=k or m=2k, k³ 1} is context-free but not deterministic.