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 |
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 |
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 | ϕ | ϕ |
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: 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 2n 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 3rd 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* | ϕ | ϕ |
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] |
[AD], [ABD], [ACD] and [ABCD] because they include D, final state of NFA.
Step 4:
Now create new DFA from the new transition table
