Nondeterministic FiniteState Acceptors
Nondeterministic finitestate acceptors (NFA), or nondeterministic finite automata, are similar to deterministic finitestate acceptors except that there may be more than one possible state that is attainable from a given state for the same input character.
Table 41
State 

Input 
0 
1 

S 
B 
A 
A 
C 
S 
B 
S 
C 
C 
A 
B 
Table 42 Traces of two strings using the DFA
Input string 

110101 

11101 
M(S, 110101) = A/(/U0101) 
M(S,11101) = M(A,1101) 

= M(S, 0101) 
= Af(5,101) 

= A/(fl,101) 
= M(A,01) 

= M(C, 01) 
= M(C, 1) 

= M(A, 1) 
= M(B,e) 

= M(S, e) 
= B (reject) 

= S (accept) 
Thus an ambiguity seems to arise because the acceptor has several possibilities to choose from. However, the acceptor is considered to explore all possibilities, one at a time, to determine if a string should be accepted. Consider the NFA given in Fig. 46 which accepts strings of the form amb" where m, n > 1. A string will be accepted by the NFA if at least one valid sequence of state transitions exists such that the acceptor is in a final state when the entire string has been read. From the finitestate diagram, it should be observed that in order for the acceptor to accept a string if possible, it stays in state A until the final character a is read. The acceptor then changes to state B. Similarly, the NFA stays in state B until the final character b is read, causing a transition to state C.
Definition 43 A nondeterministic finitestate acceptor is a 5tuple (K, VT, M, S, Z) where:
A" is a finite, nonempty set of states.
VT is an input alphabet.
M is a mapping of K X VT into subsets of is the starting state, is the set of final states.
Notice that the mapping function M is similar to that for a DFA except that M maps into a possibly empty set of states. Hence we write M(Q,T) = {Px, P2,…, Pn} where a transition from state Q to one of the states Px, P2,…,P„ occurs when a character T from VT is read. The mapping function for an NFA is extended with the following definitions:
Figure 46 An example of a nondeterministic finitestate acceptor.
The first definition implies that for the empty string, the acceptor must stay in the same state. The meaning of the second definition is less obvious. If M(Q, T) = {Px, P2,.. , P„], then the second definition can be written as M(Q,Tt) =
Thus, M(Q,Tt) is the set of all possible states that the acceptor may end up in after the string Tt has been read. The third definition extends the mapping function toand defines the mapping to be the union of all the sets resulting from applying each individual state from the set of states to the string x.
A string x is said to be accepted by an NFA if at least one of the states attainable from the starting state by reading x is a final state; that is, x is accepted by the NFA F = (K, VT, M, S, Z) if for some statethen
As an example of an NFA, consider a machine which accepts the set of strings in {a,b,c}* such that the last symbol in the input string also appears earlier in the string. For example, bab is accepted but cbbca is not. The finitestate diagram for this acceptor is given in Fig. 47. For M as defined in Table 43, the acceptor is given as
With the input string aca, the value of M(q0, aca) can be determined as follows:
Table 43 Transition table for a nondeterministic finitestate acceptor
State 

Input symbol 

a 
. h 
c 

Figure 47 Transition diagram for a nondeterministic finitestate acceptor.
Now
so
Hence
and sincethe string aca is accepted.
It should be emphasized that although a nondeterministic machine does not have unique moves, it does not contain a random device for choosing its move. Rather, the acceptor explores all possible move sequences, and if at least one of these sequences leads to a final state, then the input string is accepted.
While it might seem likely that nondeterministic finitestate acceptors are more powerful than deterministic acceptors, the following theorem proves that such is not the case. The theorem also provides a method for converting an NFA to a DFA.
Theorem 41 Letbe a nondeterministic finitestate acceptor accepting a set of strings L. Define a DFA as follows:
1. The alphabet of states consists of all the subsets of K. An element of K’ is denoted as [S1( S2,..., S1,], where Sv S2,…,SI are states of K. The states Sx, S2,…,SI are in the same canonical order, so that for some states in K, {S1,S2}(= {S2,S,}) is always S2].
2. The set of input characters VT is the same for F and F’.
3. The mapping M’ is defined as
where
4. If the starting state of F is S„ then S’ = [5,].
5. Z’ is the set of all states in K’ containing a final state in Z.
Then the set of strings accepted by F’ is the same as that for F.
Proof It must be shown that L(F’) = L(F) with the construction given in the theorem. Thus it is necessary to show that M’(S’, x) = P2,…, PJ is equivalent to M(S, x) = {Pv P2,…, P,}. This can be done by induction on the length of the string x. The result is trivial for x = 0, since x = e and S’ = [S] from the mapping M(S,e)= {5}.
Assume that M’(S’,x) is equivalent to M(S,x) forThen for
By the inductive hypothesis
is equivalent to
By definition, we have
is equivalent to
Thus the equivalence holds for
and
Thus the equivalence holds for
is equivalent to
Thus
The construction given in the theorem may be applied to any NFA. For example, the NFAwhere the mapping
function is defined in Table 44, can be converted to a DFA as follows: Define
where VT is the same as for F and the starting state is The states of K’ are initially defined asand the mapping M’ is readily obtained from the transition table for F. The mapping of these states is
A new state
is created and from the mapping of F
the mapping M’ is defined as
Similarly, the new state [<7lt q2] is added to K’ and the mappings
are defined. As no new states were created with the last mapping definitions, the creation of the DFA is nearly complete. The set of final states of F’, which is all that is left to be defined, are those states of K’ which contain an element of Z. In this example,
The notion of a nondeterministic finitestate acceptor is extended to include state transitions with the empty string as input in the next subsection. The next subsection also shews that such an acceptor is no more powerful than an acceptor which cannot change state when reading the empty string.
Nondeterministic FiniteState Acceptors with eTransitions
In this subsection, nondeterministic finitestate acceptors are allowed to have state transitions with the empty string used as input. As might be expected, such an acceptor is no more powerful than the finitestate acceptors introduced in the previous subsections.
Table 44
State 

Input 
a 
b 

Figure 48 A nondeterministic finitestate acceptor with ftransitions
Rather, it is a convenient construct for representing regular expressions.
The transition diagram for an NFA with etransitions is given in Fig. 48. This machine accepts strings of the form 1"’0" where m, n > 0. After reading a sequence of Is from the input string, the acceptor changes to state q{, before reading the 0s which follow. This is done by reading the empty string which is found between the last 1 and the first 0.
Definition 44 A nondeterministic finitestate acceptor with etransitions is a 5tuple (K,Vt,M,S,Z), where K, VT, S, and Z are the same as in Definition 43 and M is the mappinginto subsets of K.
Using this definition, the NFA depicted in Fig. 48 can be defined as
with the mapping function defined by Table 45.
Before the equivalence of an NFA with etransitions and an NFA without etransitions can be proved, it is necessary to define etransitions and define the mapping function for M(q,x) where .
Definition 45 eCLOSURE is a set of states of an NFA with etransitions, say F, such that eCLOSURE for some state of F, call it q, includes all states attainable from that state by making state transitions with etransitions. This is denoted by eCLOSURE(^).
In the example of Fig. 48,and
Notice thatfor some state q invariably includes that state because a state can always be thought of as having an etransition to itself. Furthermore,for a set of states P. The definition ofallows the mapping function to be extended with the definitions:
Table 45

Input 


State 
0 
1 
E 
The first definition states what the mapping of a state to a set of siates is when the empty string is read. In the second case, the mapping K X is defined, allowing the application of the mapping function to include strings.
It is now possible to show the equivalence of NFAs with etransitions to those without. The proof of the following theorem gives the method for constructing an NFA without etransitions.
Theorem 42 Defineas an NFA with etransitions.
Then there exists an NFA F’ without etransitions such that L(F) = L(F’). In other words, the languages accepted by the two acceptors are the same.
Proof Define an NFA F’ without etransitions aswhere K, VT, and S are the same as for F and
and M’(q,a) is M(q,a) forwhere M is the mapping function M of F extended to strings. By induction on x it is necessary to show that. Trivially ifthen S andif a final state is
The inductive step is as follows. Assume andThen
We must show that M’(S, x) contains a final state if and only if M(S,x) contains a final state. It was previously shown that such is the case of x = e. ConsiderBy the construction of F’, if
Table 46
Input 

State 
0 1 
Figure 49
M(S, x) contains a final state, then so does M’(S. x). We must also show the converse; that is, M(S,x) contains a final state if M’(S,x) also does. Consider M’(S,x) containing a state of Z’ other than S. Then M(S,x) must contain a corresponding final state, say, Z. This comes from the construction of F’. Furthermore, ifthen we have a state in and F also in M(S, x) because
Using the construction from the proof given above, an NFA without etransitions can be constructed from the NFA given near the beginning of this subsection. The acceptorI has its mapping function as defined in Table 46. The transition diagram for F’ is given in Fig. 49.
This section has introduced three types of finitestate acceptors with each new acceptor appearing to be more powerful than the previous one. It was proven that the languages which can be accepted by each acceptor were the same, however. The next two sections demonstrate the equivalence of regular grammars and regular expressions to finitestate acceptors. Methods to convert from a regular grammar or a regular expression to a finitestate acceptor and vice versa are also described.