# Set Substitution Method to convert NFA to DFA

We convert NFA to DFA so that we can implement the state machine represented by DFA.The method is as follows:

- First find out the state transition table
- Then take one state from the transtion table and then whenever you find out that output is not defined then put dead state there
- Create new DFA

We will understand the whole menthod step by step:

**Step 1:**

Following is the NFA for strings starting with 'a'

**Step 2:**

Create state transiton table

State | a | b |
---|---|---|

A | B | ϕ |

B | B | B |

**Step 3:**

Now create new transition table,

Rule is whenever there is ϕ, we will include one more state as dead state.

State | a | b |
---|---|---|

A | B | C |

B | B | B |

C | C | C |

*Note: Here C is a dead state***Step 4:**

Now create new DFA from the new transition table

**Note:**Do not think that in the new table we will take the states which we have already, for example

If on state A for input 'a' we go to A and B both in NFA then we will write as

State | a | b |
---|---|---|

A | AB | D |

AB | AB | B |

D | D | D |

If you did not get the point I have just mentioned then follow the below example, you will understand

**Step 1:**

Following is the NFA for strings ending with 'a'

**Step 2:**

Create state transiton table

State | a | b |
---|---|---|

A | [AB] | A |

B | ϕ | ϕ |

**Step 3:**

Now create new transition table,

Rule is whenever there is ϕ, we will include one more state as dead state.

State | a | b |
---|---|---|

A | [AB] | [A] |

[AB] | [AB] | [A] |

D | D | D |

**Note: 1**

*Here State D goes to D on both inputs so we have not written it.*

**Note: 2**

*Here State [AB] is denoted by state B and [A] is denoted by state A.*

**Step 4:**

Now create new DFA from the new transition table

*Note: If there are n states in NFA then there could be 2*^{n}states in DFA after conversion.

*Note: Final state(s) of DFA will be the one which includes final state of NFA*The proof of the above statement is explained by the below example:

**Step 1:**

Following is the NFA for strings having 3

^{rd}symbol 'a' from r.h.s.

**Step 2:**

Create state transiton table

State | a | b |
---|---|---|

A | {AB} | {A} |

B | {C} | {C} |

C | {D} | {D} |

D^{*} | ϕ | ϕ |

**Step 3:**

Now create new transition table,

Rule is whenever there is ϕ, we will include one more state as dead state.

State | a | b |
---|---|---|

[A] | [AB] | [A] |

[AB] | [ABC] | [AC] |

[AC] | [ABD] | [AD] |

[AD] | [AB] | [A] |

[ABC] | [ABCD] | [ACD] |

[ABD] | [ABC] | [AC] |

[ACD] | [ABD] | [AD] |

[ABCD] | [ABCD] | [ACD] |

**List of final states**

[AD], [ABD], [ACD] and [ABCD] because they include D, final state of NFA.

**Step 4:**

Now create new DFA from the new transition table