What is a finite state machine

Look here for definitions of technical terms in electronic data processing and information technology! Our database currently contains 2637 terms, 352 associated synonyms and other information.

Synonym (s):
Finite automata; Finite state machine; FSM


State machines are mathematical models of simple ideal calculating machines. The automata theory has many applications, e.g. in the modeling of parallel processes, in compiler construction or in the description of digital switching mechanisms.
It is a "finite" automaton because it only has a finite number of internal states and can ultimately only accept words of finite length. Finite automatons can recognize exactly the words of the so-called regular languages, which is why they are used for word recognition and especially for recognizing sets of words that are specified by regular expressions.

When parsing documents, state machines are also used for token recognition in order to condense the character stream into a token stream on which the parsing then takes place.


Function:

A finite automaton reads a finite symbol sequence (input word) from a finite set of symbols (input alphabet) and shows whether it accepts the word or not by holding or not. A finite automaton with output (Mealy or Moore automaton) also writes, according to its programming, a finite symbol sequence (output word) from a symbol set (output alphabet).

A finite automaton can be described as a finite transition system. Depending on the program that the automaton implements, it has a smaller or larger finite number of states into which it can switch. At the beginning it is in a particularly excellent starting condition. When reading the input stream and when writing the output stream, the machine proceeds step-by-step, with the next symbol of the input being read out in each step. With this input symbol and the current status produced, a finite output symbol sequence (and continuously the output) is then output in one processing step and the changeover to the new status.

In addition to this finite one-way machine (1EA), which reads the input consistently from one direction, a finite two-way machine (2EA) can also be defined, which can move the head to the left or right after reading a symbol.