Finite state machine

related topics
{math, number, function}
{system, computer, user}
{law, state, case}
{mi², represent, 1st}
{theory, work, human}
{car, race, vehicle}
{build, building, house}
{acid, form, water}
{language, word, form}
{style, bgcolor, rowspan}

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical abstraction sometimes used to design digital logic or computer programs. It is a behavior model composed of a finite number of states, transitions between those states, and actions, similar to a flow graph in which one can inspect the way logic runs when certain conditions are met. It has finite internal memory, an input feature that reads symbols in a sequence, one at a time without going backward; and an output feature, which may be in the form of a user interface, once the model is implemented. The operation of an FSM begins from one of the states (called a start state), goes through transitions depending on input to different states and can end in any of those available, however only a certain set of states mark a successful flow of operation (called accept states).

Finite-state machines can solve a large number of problems, among which are electronic design automation, communication protocol design, parsing and other engineering applications. In biology and artificial intelligence research, state machines or hierarchies of state machines are sometimes used to describe neurological systems and in linguistics—to describe the grammars of natural languages.


Full article ▸

related documents
Brute force attack
Selection sort
Fundamental theorem of arithmetic
Pell's equation
Binomial theorem
Delaunay triangulation
Polish notation
Greatest common divisor
Affine transformation
Naive Bayes classifier
Empty set
NP (complexity)
Knapsack problem
Brouwer fixed point theorem
Direct product
Net (mathematics)
Grover's algorithm
Sheffer stroke
Graph theory
Scientific notation
Shell sort
Ordered pair
Cyclic group
Tree automaton
Integer (computer science)
Partially ordered set