Nondeterministic finite automaton

In the automata theory, a nondeterministic finite automaton (NFA) or nondeterministic finite state machine is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, a NFA can be translated to equivalent DFA using powerset construction, i.e., the constructed DFA and the NFA recognize the same formal language. Both types of automata recognize only regular languages. Nondeterministic finite automata were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to deterministic finite automata.

NFAs are sometimes studied by the name subshifts of finite type. NFAs have been generalized multiple ways, e.g., probabilistic automata, which assign a probability to each state transition.

Informal introduction

A NFA, similar to a DFA, consumes a string of input symbols. For each input symbol it transitions to a new state until all input symbols have been consumed. Unlike a DFA, it is non-deterministic in that, for any input symbol, its next state may be any one of several possible states. Thus, in the formal definition, the next state is an element of the power set of states. This element, itself a set, represents some subset of all possible states to be considered at once. The notion of accepting an input is similar to that for the DFA. When the last input symbol is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state.

Formal definition

An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a transition relation Δ : Q × Σ → P(Q).
• an initial (or start) state q₀ ∈ Q
• a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q. Let w = a₁a₂ ... a_n be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r₀,r₁, ..., r_n, exists in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, the first condition says that the machine starts in the start state q₀. The second condition says that given each character of string w, the machine will transition from state to state according to the transition relation Δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

For more comprehensive introduction of the formal definition see automata theory.

Example

The state diagram for M

Let M be a NFA, with a binary alphabet, that determines if the input ends with a 1.

In formal notation, let M = ({p, q}, {0, 1}, Δ, p, {q}) where the transition relation Δ can be defined by this state transition table:

	0	1
p	{p}	{p,q}
q	{}	{}

Note that Δ(p,1) has more than one state therefore M is nondeterministic. The language of M can be described by the regular language given by the regular expression (0|1)*1.

Variations of NFA

• Deterministic finite automaton(DFA): In this automaton, for each state and alphabet, the transition relation has exactly one state.
• Nondeterministic finite automaton with ε-moves(NFA-ε): This automaton replaces the transition function with the one that allows the empty string ε as a possible input, so the transition relation is defined as Δ : Q × (Σ ∪{ε}) → P(Q).

Closure properties

If NFAs recognize the languages that are obtained by applying an operation on the NFA recognizable languages then NFAs are said to be closed under the operation. The DFAs are closed under the following operations.

• Union
• Intersection
• Concatenation
• Negation
• Kleene closure

Since NFAs are equivalent to nondeterministic finite automaton with ε-moves(NFA-ε), the above closures are proved using closure properties of NFA-ε. The above closure properties imply that NFAs only recognize regular languages.

Properties

The machine starts in the specified initial state and reads in a string of symbols from its alphabet. The automaton uses the state transition function Δ 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 automaton (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 rise in the number of necessary states. A formal proof of the powerset construction is given here.

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 (as storage of the state value requires at most one bit for every state 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 n − 1 copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)
• 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. (For an implementation that uses this technique to keep track of object references have a look at Tracematches.)

Application of NFA

NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closer properties of regular languages using NFAs than DFAs.

• The union of two regular languages is regular.
• The concatenation of two regular languages is regular.
• The Kleene closure of a regular language is regular.

References

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp.47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)