2.4 THE NFA WITH -MOVES

2.3 TRANSFORMING NFA TO DFA

For every non-deterministic finite automata, there exists an equivalent deterministic finite automata. The equivalence between the two is defined in terms of language acceptance. Since an NFA is a nothing more than a finite automata in which zero, one, or more transitions on an input symbol is permitted, we can always construct a finite automata that will simulate all the moves of the NFA on a particular input symbol in parallel. We then get a finite automata in which there will be exactly one transition on an input symbol; hence, it will be a DFA equivalent to the NFA.

Since the DFA equivalent of the NFA simulates (parallels) the moves of the NFA, every state of a DFA will be a combination of one or more states of the NFA. Hence, every state of a DFA will be represented by some subset of the set of states of the NFA; and therefore, the transformation from NFA to DFA is normally called the "construction" subset. Therefore, if a given NFA has n states, then the equivalent DFA will have 2 ⁿ number of states, with the initial state corresponding to the subset { q }. Therefore, the transformation from NFA to DFA involves finding all possible subsets of the set states of the NFA, considering each subset to be a state of a DFA, and then finding the transition from it on every input symbol. But all the states of a DFA obtained in this way might not be reachable from the initial state; and if a state is not reachable from the initial state on any possible input sequence, then such a state does not play role in deciding what language is accepted by the DFA. (Such states are those states of the DFA that have outgoing transitions on the input symbols ”but either no incoming transitions, or they only have incoming transitions from other unreachable states.) Hence, the amount of work involved in transforming an NFA to a DFA can be reduced if we attempt to generate only reachable states of a DFA. This can be done by proceeding as follows :

Let M = ( Q , & pound ; , , q , F ) be an NFA to be transformed into a DFA.

Let Q ₁ be the set states of equivalent DFA.

begin:

  Q   1old  =    Q   1new  = {q   }     While (  Q   1old     Q   1new  )     {        Temp = Q  1new  - Q  1old   Q   1  =  Q   1new  for every subset  P  in Temp do                for every a in   do                         If transition from  P  on  a  goes to new subset  S  of  Q  then                         (transition from  P  on a is obtained by finding out                         the transitions from every member of  P  on  a  in a given                         NFA                         and then taking the union of all such transitions)  Q   1   new  =  Q   1   new    S     }  Q   1  =  Q   1new  end 

A subset P in Q _l will be a final state of the DFA if P contains at least one member of F of the NFA. For example, consider the following finite automata:

where:

The DFA equivalent of this NFA can be obtained as follows:

		1
{ q )	{ q 1 }
{ q 1 }	{ q 1 }	{ q 1 , q 2 }
{ q 1 , q 2 }	{ q 1 }	{ q 1 , q 2 , q 3 }
*{ q 1 , q 2 , q 3 }	{ q 1 , q 3 }	{ q 1 , q 2 , q 3 }
*{ q 1 , q 3 }	{ q 1 , q 3 }	{ q 1 , q 2 , q 3 }

The transition diagram associated with this DFA is shown in Figure 2.3.

Figure 2.3: Transition diagram for M = ({q , q ₁ , q ₂ , q ₃ }, {0, 1} , q , {q ₃ }).