Converting an NFA to a DFA - Example

Consider the following NFA

  Q = states = {1,2,3,4,5}
  Start state: { 1 }
  Accepting state(s): { 5 }

Now construct an equivalent DFA.

• The states of the DFA will be determined by subsets of the states of the NFA.
• Unfortunately, there are 2⁵ = 32 different subsets of Q. Here are some of them:

   Q/ = states for the DFA
   Some states in Q/:
   Empty set, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, ..., {1,2,3,4,5}
  

• But not all will be reachable from the start state of the DFA to be constructed.
• The start state is the ε-closure of the start state of the NFA.
• The final states of the DFA will correspond to the subsets of the NFA that contain a final state.

The ε-closure of a set of states, R, of the NFA will be denoted by E(R).

 E(R) = R ∪ { q | there is an r in R with an ε transition to q }

 In the example, E({1}) = {1} ∪ { 2 } = {1,2}

Construction

1. Compute the start state: E({1}) = {1,2}
2. Start a table for the transition function or draw a diagram with {1,2} but only containing the start state:

   

   	a	b
   {1,2}

3. Compute the transition function for the DFA from the start state.
   1. For one of the inputs, say 'a', consider all possible states that can be reached in the NFA from any one of the states in {1,2} on input 'a'. These are states that are reachable along paths labeled 'a', also allowing any edges labeled ε.

      For example,

      
      
       DFA state {1,2}
       From 1, we have
                a path from 1 to 3 labeled 'a': 1 a 3
                a path from 1 to 4 labeled ε 'a': 1 ε 2 'a' 4
                a path from 1 to 5 labeled ε 'a': 1 ε 3 'a' 5
       From 2, we have
                a path from 2 to 4 labeled 'a': 2 'a' 4
                a path from 2 to 5 labeled 'a': 3 'a' 5
      
      So altogether we can reach {3,4,5} from {1,2} on input 'a'
      

      	a	b
      {1,2}	{3,4,5}

   2. Next compute the transitions from the start state with input 'b'. But when the NFA transitions are examined there are no paths from either state in {1,2} with label 'b'. So the subset of states that can be reached is the empty set, ∅.

      	a	b
      {1,2}	{3,4,5}	∅

4. If a new state is reached when the transitions on 'a' and 'b' are computed, the process has to be repeated this new state. For example, {3,4,5} is a new state for the DFA and so we must compute transitions from this state.

   
    DFA state {3,4,5}, input 'a'
    From 3, we have no transition paths labeled 'a'
    From 4, 
             a path from 4 to 5 labeled 'a': 4 a 5
    From 5, there are no transition paths labeled 'a'
   
    So altogether we can reach {5} from {3,4,5} on input 'a'
   
    DFA state {3,4,5}, input 'b'
    From state 3, a path from 3 to 4 labeled 'b': 3 b 4
    From state 4, a path from 4 to 5 labeled 'b': 4 b 5
    From 5, there are no transition paths labeled 'b'
   
    So altogether we can reach {4,5} from {3,4,5} on input 'b'
   

   Filling in the table we get:

   	a	b
   {1,2}	{3,4,5}	∅
   {3,4,5}	{5}	{4,5}

5. Continuing filling in the table as long as any states are entered that do not yet have a row. For example neither {5} or {4,5} have a row yet. So pick one and compute its transitions.

   The final states of the DFA are the sets that contain 5 since that is the only final state of the NFA.

   The final table and corresponding DFA state diagram are:

   	a	b
   {1,2}	{3,4,5}	∅
   {3,4,5}	{5}	{4,5}
   {5}	∅	∅
   {4,5}	{5}	{5}
   ∅	∅	∅