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.
State diagram
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 |
Outputs
There are different variants, for instance,
- Moore machine - machines having actions (outputs) associated with states.
- Mealy machine - machines having actions (outputs) associated with transitions.
Mathematical Model
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.
