- Q is a finite set of
*states,* - is a finite set of
symbols, the
*input alphabet,* - is either a
*stack alphabet*or a*tape alphabet*, - is a
*transition function,* - q
_{0}Q is the*initial state,* - z
is the
*stack start symbol,* - #
is a symbol called
*blank*, - F Q is
a set of
*final states.*

A **nondeterministic finite-state acceptor (nfa)** is the
same quintuple with transition function

A **nondeterministic pushdown automaton (npda)**
is a 7-tuple

A **Turing machine** M (also a **linear-bounded automaton**,
or **lba**) is a 7-tuple

Copyright © 1996 by David Matuszek

Last modified Apr 24, 1996