Automata

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:
  1. First find out the state transition table
  2. Then take one state from the transtion table and then whenever you find out that output is not defined then put dead state there
  3. 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
Stateab
ABϕ
BBB
Step 3:
Now create new transition table,
Rule is whenever there is ϕ, we will include one more state as dead state.
Stateab
ABC
BBB
CCC
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
Stateab
AABD
ABABB
DDD

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
Stateab
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.
Stateab
A[AB][A]
[AB][AB][A]
DDD
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 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
Stateab
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.
Stateab
[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





Quantitative Aptitude
Reasoning
Programming
Interview