Nondeterministic finite state machine
|
|
In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states.
Intuitive explanations
This article assumes an understanding of the deterministic finite state machine. Such a machine has a collection of states. At each point in time it determines which state to visit next based only on its current state and the next input character. The primary difference with a nondeterministic machine is that it can potentially encounter a situation where it can make multiple choices. For example, if it's in state 2 and sees an a, it might be able to proceed to either state 3 or state 4. It even has the ability to proceed from one state to another without consuming any input — the edges it follows in doing so are called epsilon edges, because they are usually labelled with the Greek letter ε. Again, it may have a choice between following such an edge or following an edge that does consume input.
How do we know whether such a machine accepts? The choices it makes at each point in time will determine whether, at the end, it ends up in an accepting state. We define that a nondeterministic finite state machine accepts if and only if there is some set of choices it could make that will take it to an accepting state. Equivalently, it rejects only if it would reject no matter what choices it makes.
Another way of thinking about a nondeterministic finite state machine is that whenever it has a choice, it "forks", or makes copies of itself at that instant in time, and each selects one of the paths forward. In this model, the accepting condition is that at least one of the resulting copies is in an accepting state when it stops.
Formal definition
A NFA is a 5-tuple, (S, Σ, T, s, A), consisting of
- a finite set called the alphabet (Σ)
- a finite set of states (S)
- a transition function (T : S × (Σ ∪{ε}) → P(S)).
- a start state (s ∈ S)
- a set of accept states (A ⊆ S)
where P(S) is the power set of S and ε is the empty string.
Let M be an NFA such that M = (S, Σ, T, s, A), and X be a string over the alphabet Σ. M accepts the string X if there exist both a representation of X of the form x1x2 ... xn, xi ∈ (Σ ∪{ε}), and a sequence of states r0,r1, ..., rn, ri ∈ S, meeting the following conditions:
- r0 = s
- ri ∈ T(ri-1, xi), for i = 1, ..., n
- rn ∈ A.
The machine starts in the start state and reads in a string of symbols from its alphabet. It uses the transition relation T to determine the next state(s) using the current state and the symbol just read or the empty string. If, when it has finished reading, it is in an accepting state, it is said to accept the string, otherwise it is said to reject the string. The set of all strings accepted by an NFA is the language the NFA accepts.
The language accepted by a NFA is a regular language.
For every NFA a deterministic finite state machine (DFA) can be found that accepts the same language. Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction which may lead to an exponential raise in the number of necessary states. Such determinization however is necessary to build a complement automaton.
Example
The following example explains a NFA M, with a binary alphabet, which determines if the input contains an even number of 0s or an even number of 1s.
M = (S, Σ, T, s, A) where
- Σ = {0, 1},
- S = {S0, S1, S2, S3, S4},
- s = S0,
- A = {S1, S3}, and
- The transition function T can be defined by this state transition table:
0
| 1
| ε
| |
S0
| {}
| {}
| {S1, S3}
|
S1
| {S2}
| {S1}
| {}
|
S2
| {S1}
| {S2}
| {}
|
S3
| {S3}
| {S4}
| {}
|
S4
| {S4}
| {S3}
| {}
|
The state diagram for M is:
M can be viewed as the union of two DFAs: one with states {S1, S2} and the other with states {S3, S4}.
The language of M can be described by the regular language given by this regular expression:
- <math>(1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*) <math>de:Nichtdeterministischer endlicher Automat
he:אוטומט סופי לא דטרמיניסטי pl:Niedeterministyczny automat skończony