Nondeterministic finite state machine - Definition and Overview

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 Σ. M accepts the string X if there exist both a representation of X of the form x₁x₂ ... x_n , x_i ∈ (Σ ∪{ε}), and a sequence of states r₀,r₁, ..., r_n, r_i ∈ S, meeting the following conditions:

1. r₀ = s
2. r_i ∈ T(r_i-1, x_i), for i = 1, ..., n
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 all strings accepted by an NFA is the language the NFA accepts.

The language accepted by a NFA is a regular language.

Every NFA has an equivalent deterministic finite state machine (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:

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>