Machines and Functions

A deterministic finite-state acceptor (dfa) is a quintuple
M = (Q, sigma, delta, q0, F)
with transition function
delta: Q cross product sigma goes to Q
and extended transition function
deltastar: Q cross product sigmastar goes to Q

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

delta: Q cross product ( sigma union { empty string } ) goes to 2superscript Q

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

M = (Q, sigma, gamma, delta, q0, z, F)
with transition function
delta: Q cross product (sigma union {empty string}) cross product gamma goes to finite subsets of Q cross product gamma*

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

(Q, sigma, gamma, delta, q0, #, F)
with partial transition function
delta: Q cross product gamma goes to Q cross product gamma cross product {L, R}


Copyright 1996 by David Matuszek
Last modified Apr 24, 1996