A finite state machine or automation provides a simple model of computation, a way to reduce the complexities of a computer to its essence, in addition to its theoretical significance this can be a good way to tackle certain types of practical problem.
The current state is determined by past states of the system and the inputs to the system (it has a memory). A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition. An action is a description of an activity that is to be performed at a given moment.
We could describe the machine in terms of transitions, for each combination of state and input this will determine the transition function which gives the next state:
State transition table
|Condition↓Current state ->||State 1||State 2||State 3||State 4||State 5||State 6|
|Input red||State 2||State 3||State 1||State 5||State 6||State 4|
|Input blue||State 4||State 5||State 6||State 1||State 2||State 3|
There are different variants, for instance,
- Moore machine - machines having actions (outputs) associated with states.
- Mealy machine - machines having actions (outputs) associated with transitions.
In its essence the model consists of (Σ,S,s0,δ), where:
- Σ is the input alphabet (a finite, non-empty set of symbols).
- S is a finite, non-empty set of states.
- s0 is an initial state, an element of S.
- δ is the state-transition function: δ: S × Σ -> S (in a nondeterministic finite state machine it would be δ: S × Σ -> (S1,S2,S3,S4) i.e., δ would return a set of states).
In some circumstances (for instance Mealy machine) we may need to add:
- F - the set of final states (subset of S) states, if any that result in the machine stopping.
- Γ - the output alphabet (a finite, non-empty set of symbols).
- ω - the output function - a mapping from the states to output.