- The transition function
is single-valued for a dfa, multi-valued for an nfa.
- An nfa may have -transitions.

- The transition function
is
*at most*single-valued for a dpda, multi-valued for an npda.Formally: |(q, a, b)| = 0 or 1,

for every q Q, a {}, and b . - Both npdas and dpdas may have -transitions;
but a dpda may have a -transition
only if no other transition is possible.
Formally: If (q, , b) ,

then (q, c, b) = for every c .

The deterministic context-free languages are a proper subset of the context-free languages.

Copyright © 1996 by David Matuszek

Last modified Mar 18, 1996