Deterministic finite state machine
|
|
In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is a deterministic next state.
Formal definition
A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of
- a finite set of states (S)
- a finite set called the alphabet (Σ)
- a transition function (T : S × Σ → S).
- a start state (s ∈ S)
- a set of accept states (A ⊆ S)
Let M be a DFA such that M = (S, Σ, T, s, A), and X = x1x2 ... xn be a string over the alphabet Σ. M accepts the string X if a sequence of states, r0,r1, ..., rn, exists in S with the following conditions:
- r0 = s
- ri+1 = T(ri, xi), for i = 0, ..., n-1
- rn ∈ A.
As shown in the first condition, the machine starts in the start state s. The second condition says that given each character of string X, the machine will transition from state to state as ruled by the transition function T. The last condition says that the machine accepts if the last input of X causes the machine to be in one of the accepting states. Otherwise, it is said to reject the string. The set of strings it accepts form a language, which is the language the DFA recognises.
Example
The following example is of a DFA M, with a binary alphabet, which determines if the input contains an even number of 0s.
M = (S, Σ, T, s, A) where
- Σ = {0, 1},
- S = {S1, S2},
- s = S1,
- A = {S1}, and
- T is defined by the following state transition table:
| 0 | 1
| |
| S1 | S2 | S1 |
| S2 | S1 | S2 |
The state diagram for M is:
- Missing image
DFAexample.png
Image:DFAexample.png
Simply put, the state S1 represents that there has been an even number of 0s in the input so far, while S2 signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not.
The language of M can be described by the regular language given by this regular expression:
- <math>1^*(01^*01^*)^* \,\!<math>
See also
he:אוטומט סופי דטרמיניסטי pl:Deterministyczny automat skończony