NFA to DFA using Indirect method
Step 01 : First convert NFA with ∈ moves to NFA without ∈ moves.
Step 01 :Then convert NFA without ∈ to the DFA.
Let's take an example,
We have a NFA with epsilon moves, now convert it to the NFA without epsilon moves.
 |
| NFA with epsilon moves |
First convert above NFA to without epsilon moves,
Find ∈-closure of (q1), (q2) and (q3).
- ∈-closure of (q1) = {q1, q2, q3}
- ∈-closure of (q2) = {q2, q3}
- ∈-closure of (q3) = {q3}
|
State |
0 |
1 |
2 |
|
->q1 |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
q2 |
φ |
{q2,q3} |
{q3} |
|
q3 |
φ |
φ |
{q3} |
From the above transition table, draw the transition diagram,
 |
| NFA without epsilon |
From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.
So, now without ∈ input, q1 and q2 is also treated as final states.
As shown in diagram beabove.
Now, NFA without epsilon to DFA
Using Subset construction method.
Again I am going to use information from this transition table.
|
State |
0 |
1 |
2 |
|
->q1 |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
q2 |
φ |
{q2,q3} |
{q3} |
|
q3 |
φ |
φ |
{q3} |
Subsets are,
- {q1}
- {q2}
- {q3}
- {q1,q2,q3}
- {q2,q3}
Treat each subset as state in DFA.
If there is no transition use φ symbol.
|
State |
Input = 0 |
Input = 1 |
Input = 2 |
|
{q1} |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
{q2} |
φ |
{q2,q3} |
{q3} |
|
{q3} |
φ |
φ |
{q3} |
|
{q1,q2,q3} |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
{q2,q3} |
φ |
{q2,q3} |
{q3} |
|
φ |
φ |
φ |
φ |
In NFA withoud epsilon, q1, q2, q3 was final states. In subset {q1,q2,q3} and {q2,q3} final states exist.
So these subsets will also treated as final states.
 |
| DFA from NFA |
Now from the transition table of above DFA,
|
State |
Input = 0 |
Input = 1 |
Input = 2 |
|
{q1} |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
{q2} |
φ |
{q2,q3} |
{q3} |
|
{q3} |
φ |
φ |
{q3} |
|
{q1,q2,q3} |
{q1,q2,q3} |
{q2,q3} |
{q3} |
|
{q2,q3} |
φ |
{q2,q3} |
{q3} |
|
φ |
φ |
φ |
φ |
We find state {q1,q2,q3} is equivalent to state {q1}, so replce state {q1,q2,q3} by state {q1}.
Simillary, replace state {q2,q3} by state {q2}.
So, new DFA transition table become,
|
State |
Input = 0 |
Input = 1 |
Input = 2 |
|
{q1} |
{q1} |
{q2} |
{q3} |
|
{q2} |
φ |
{q2} |
{q3} |
|
{q3} |
φ |
φ |
{q3} |
|
φ |
φ |
φ |
φ |
And DFA transition diagram,
Post a Comment
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.