[Overview] [Previous] [Next]

Machines and Functions

• 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₀ Q is the initial state,
• z is the stack start symbol,
• # is a symbol called blank,
• F Q is a set of final states.

M = (Q, , , q₀, F)

: Q Q

: Q Q

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

: Q ( { } ) 2

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

M = (Q, , , , q₀, z, F)

: Q ( {}) finite subsets of Q *

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

(Q, , , , q₀, #, F)

: Q Q {L, R}