Finite State Machine

Definition: A ModelOfComputation consisting of a set of states, a start state, an input alphabet, and a transition function which maps input symbols and current states to a next state. Computation begins in the start state with an input string. It changes to new states depending on the transition function. There are many variants, for instance, machines having actions (outputs) associated transitions (MealyMachine?) or states (MooreMachine?), multiple start states, transitions conditioned on no input symbol (a null) or more than one transition for a given symbol and state (nondeterministic finite state machine), one or more states designated as accepting states (recognizer), etc.

Also known as FiniteStateAutomaton or FiniteAutomaton?. Part of the ChomskyHierarchy.

Parroted from http://www.nist.gov/dads/HTML/finiteStateMachine.html

All digital electronics (wristwatches, CPUs, RAM, pacemakers, etc.) are finite state machines. Some people speculate that the entire universe is a finite state machine.

One studies FSMs and other machines in AutomataTheory?, a college class with no shortage of greek letters.

Finite state machines find practical application in lexical analyzers and parsers, where they may have tens or even hundreds of states.

Most parsers are implemented using PushdownAutomata?, not FiniteStateMachines. FSMs cannot handle context-free grammars; virtually all high-level languages have a grammar which (ignoring semantic actions) is context-free.

(Really? But I thought a computer is a FSM, and it seems to handle ContextFreeGrammar? just fine.)

Technically, a computer is a FiniteStateMachine, but one with an incredibly large number of states. As such, it can be used to model TuringMachines and PushdownAutomata?, and the modelling is exact--that is, until you get an out of memory error. (At which point, if you add more memory, the illusion will be again preserved until that memory is exhausted). For many practical problems, the spell is never broken.

Do you know where I could find a diagram of one of these lexical finite state machines?

You can write one yourself with a tool such as lex.

You can find a FiniteStateMachine simulator at http://www.belgarath.org/java/fsme.html.

See also State Machine Compiler at http://smc.sf.net

Just Gotta see TheDragonBook: Principles of Compiler Design Aho, Ulmann, and crew. --gl

RAM can be thought of as a (very simple) finite state machine, with a vast number of states. A CPU can be thought of as a (somewhat more complex) finite state machine, but with fewer internal states. A ROM can be considered an even more complicated FSM (MealyMachine?) with only one state.

At times it is convenient to think of 2 or more interacting finite state machines ("CPU" and "RAM" for example) as a single larger finite state machine ("a computer").

In theory, a computer is a finite state machine where the state space is the total possible configurations of memory. This would be two raised to the power of the total number of bits of storage.

When actually building hardware, it's usually easier/cheaper to build several smaller FSMs and link them together than to build the large machine directly. For example, CPUs are usually designed as a collection of little bits of RAM and ROM and ALUs and other FSMs glued together with the "control logic" finite state machine -- each FSM fairly trivial when considered by itself.

But a computer is modeled as a TuringMachine, even though they do have finite memory. Until you run OUT of memory, there isn't much of a difference.

See: InfiniteStateMachine, StateMachine, StateMachinesAreBetter