Finite-state machines

Finite-state machines are a mathematical abstraction for modeling computable functions and grammars for formal (programming) languages.There are four major types of finite state machines corresponding to the types of formal languages

• Finite-state automata, corresponding to Type 3 (regular) languages
• Pushdown automata, corresponding ot Type 2 (context-free) languages
• Linear bounded automata, corresponding to type 1 (context-sensitive) languages
• Turing machines, corresponding to Type 0 formal languges

A finite-state machine consists of an infinite tape, a finite set of states, a finite set of symbols (an alphabet), a start state, a subset of the set of states (the final states), and a set of state transitions.  Finite-state machines differ in the form of a state transaction and the action that the machine can perform.  If there is no state transition matching what the machine currently has, the machine stops.  If any configuration of the machine matches two or more state transitions, the machine is non-deterministic, otherwise the machine is deterministic.   For a finite-state machine that recognizes strings in a formal language, the string is accepted if and only if, given a tape containing the string to be recognized, the machine stops in a final state.

For a finite-state automaton, the state transitions map a state and a symbol to a state.  No other actions can be performed.  Symbols on the tape are read from left to right.

For a Turing machine, the machine can write over the current symbol and move the tape left or right one cell, or not move the tape.  The state transitions map a state and a symbol to a state, a symbol, and a motion of the tape.

A linear-bounded automaton is similar to a Turing machine except that the string to be recognized is preceded and followed by symbols that are not in the alphabet and cannot be overwritten; the machine must remain on one of or between these symbols.

A pushdown automaton has auxiliary storage in the form of a pushdown stack; the machine can push an alphabet symbol on to the stack, pop an alphabet symbol off the stack, or leave the stack unchanged.  The state transitions map a state, tape symbol, and stack symbol to a state and stack action.  Symbols on the tape are read from left to right.