Construct a minimum state automata equivalent to given automata ?
(RGPV 2008)
Solution:
Transition table for above automata.
|
State |
Input = a |
Input = b |
|
->q0 Initial state |
q1 |
q3 |
|
q1 |
q2 |
q4 |
|
q2 |
q1 |
q1 |
|
q3 |
q2 |
q4 |
|
q4 Final state |
q4 |
q4 |
Step 01: Remove steps which are unreachable from initial states.
Step 02: Split final states and non final states.
A0 = {q4}
A1 = {q0,q1,q2,q3}
π0 = {q4}, {q0,q1,q2,q3}
A0 cannot be partition further.
In A1,
q0 is 1 equivalent to q2 for input a, but not equivalent to q1 and q3.
q1 is 1 equivalent to q3 for input a and b, but not to q0 and q2.
So, A1 can be partitioned as,
B0 = {q0, q2}
B1 = {q1, q3}
π1 = {q4}, {q0,q2}, {q1,q3}
Now, B0 and B1 can not be partitioned further.
π2 = {q4}, {q0,q2}, {q1,q3}
π2 = π1
In minimized DFA, we have three states,
- {q4},
- {q0,q2},
- {q1,q3}
|
State |
Input = a |
Input = b |
|
->{q0,q2} Initial state |
{q1,q3} |
{q1,q3} |
|
{q1,q3} |
{q0,q2} |
{q4} |
|
{q4} Final state |
{q4} |
{q4} |
