Non-Deterministic Finite Automata

If the basic finite automata model is modified in such a way that from a state on an input symbol zero, one or more transitions are permitted, then the corresponding finite automata is called a "non-deterministic finite automata" (NFA). Therefore, an NFA is a finite automata in which there may exist more than one paths corresponding to x in Σ* (because zero, one, or more transitions are permitted from a state on an input symbol). Whereas in a DFA, there exists exactly one path corresponding to x in Σ*. Hence, an NFA is nothing more than a finite automata:

in which δ defines mapping from Q � Σ to 2^Q (to take care of zero, one, or more transitions). For example, consider the finite automata shown below:

where:

The transition diagram of this automata is:

Figure 1: Transition diagram for finite automata that handles several transitions.

Acceptance of Strings by Non-deterministic Finite Automata

Since an NFA is a finite automata in which there may exist more than one path corresponding to x in Σ*, and if this is, indeed, the case, then we are required to test the multiple paths corresponding to x in order to decide whether or not x is accepted by the NFA, because, for the NFA to accept x, at least one path corresponding to x is required in the NFA. This path should start in the initial state and end in one of the final states. Whereas in a DFA, since there exists exactly one path corresponding to x in Σ*, it is enough to test whether or not that path starts in the initial state and ends in one of the final states in order to decide whether x is accepted by the DFA or not.

Therefore, if x is a string made of symbols in Σ of the NFA (i.e., x is in Σ*), then x is accepted by the NFA if at least one path exists that corresponds to x in the NFA, which starts in an initial state and ends in one of the final states of the NFA. Since x is a member of Σ* and there may exist zero, one, or more transitions from a state on an input symbol, we define a new transition function, δ₁, which defines a mapping from 2^Q � Σ* to 2^Q; and if δ₁ ({q₀},x) = P, where P is a set containing at least one member of F, then x is accepted by the NFA. If x is written as wa, where a is the last symbol of x, and w is a string made of the remaining symbols of x then:

For example, consider the finite automata shown below:

where:

If x = 0111, then to find out whether or not x is accepted by the NFA, we proceed as follows:

Since δ₁ ({q₀}, 0111) = {q₁, q₂, q₃}, which contains q₃, a member of F of the NFA—, hence, x = 0111 is accepted by the NFA.

Therefore, if M is a NFA, then the language accepted by NFA is defined as:

L(M) = {x | δ₁ ({q₀} x) = P, where P contains at least one member of F }.