Nondeterministic finite state machine
In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton is a
finite state machine where for each pair of state and input symbol there may be several possible next states.
Encyclopedia
In the theory of computation, a
nondeterministic finite state machine or
nondeterministic finite automaton is a
finite state machine where for each pair of state and input symbol there may be several possible next states.
Intuitive explanations
A NFA consumes a string of input symbols. For each input symbol it transforms to a new state until all input symbols have been consumed.
It is non-deterministic because it may encounter a situation where there are multiple transformations out of a state by using the same letter. For NFA-lambda it is also possible to transform to a new state without consuming any input symbols. For example, if it's in state 1, with the next input symbol an
a, it can move to state 2 without consuming any input symbols and can enter state 3 by consuming an
a. It is unable to determine the correct state to enter, or rather it enters both states.
Transformations to new states without consuming an input symbol are called
lambda transitions or
epsilon transitions. They are usually labelled with the Greek letter ? or e.
When the last input symbol is consumed the NFA accepts if and only if there is
some set of transitions it could make that will take it to an accepting state. Equivalently, it rejects if no matter what choices it makes it would not end in an accepting state.
Formal definition
A nondeterministic finite state automaton is a 5-tuple,
, consisting of
- a finite set of states
- a finite set of input symbols
- a transition function .
- a set of states s0 distinguished as initial states
- a set of states A distinguished as accepting states
where
P is the power set of
S, e is the empty string, and S is the input symbol alphabet.
Let
M be an NFA such that
M = , and
X be a string over the alphabet S.
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 ? s0
- ri ? T, for i = 1, ..., n
- rn ? A.
The machine starts in an arbitrary initial state and reads in a string of symbols from its alphabet. The automaton uses the transition relation T to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in" . If, when the automaton has finished reading, it is in an accepting state, the NFA 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. This language is a regular language.
For every NFA a
deterministic finite state machine 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 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.
Implementation
There are many ways to implement a NFA:
- Convert to the equivalent DFA. In some cases this may cause exponential blowup in the size of the automaton and thus auxiliary space proportional to the number of states in the NFA
- Keep a set data structure of all states which the machine might currently be in. On the consumption of the last input symbol, if one of these states is a final state, the machine accepts the string. In the worst case, this may require auxiliary space proportional to the number of states in the NFA; if the set structure uses one bit per NFA state, then this solution is exactly equivalent to the above.
- Create multiple copies. For each n way decision, the NFA creates up to copies of the machine. Each will enter a separate state. On the consumption of the last input symbol and one copy of the NFA is in the accepting state the NFA will accept.
- Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition.
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 = where
The
state diagram for
M is:
M can be viewed as the union of two
DFAs: one with states and the other with states .
The language of
M can be described by the regular language given by this regular expression:
References
- Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.2: Nondeterminism, pp.47–63.
