Non-deterministic finite automaton

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.

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 Σ that can be written as x₁x₂ ... x_n where each x_i ∈ (Σ ∪{ε}). M accepts the string X if a sequence of states, r₀,r₁, ..., r_n, exists in S with the following conditions:

1. r₀ = s
2. r_i+1 ∈ T(r_i, x_i+1), for i = 0, ..., n-1
3. r_n ∈ 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 strings it accepts form a language, which is the language the NFA recognises.

Every NFA has an equivalent DFA. 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.

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 = {S₀, S₁, S₂, S₃, S₄},
• s = S₀,
• A = {S₁, S₃}, 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 {S₁, S₂} and the other with states {S₃, S₄}.

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>