Reducing a DFA using the Pair Table method

Question

I'm learning about reducing DFA's using the Pair Table Method (Systematic Reduction Method).Here is the DFA we are looking to reduce.

The first step is to lay out the DFA in a table:

                                    0           1
             q0                  {q0, q3}      {q1}
             q1                    {q2}        {q2}
             q2                  EmptySet      {q2}
          {q0, q1}             {q0, q1, q3}    {q1, q2}
          {q1, q2}                 {q2}        {q2} 
        {q0, q1, q2}           {q0, q1, q2}    {q1, q2} 

We don't need to include the empty set state, I think.

Now here is where I'm confused, I need to go through the list of states and mark them based on something. I'm not sure how to proceed.

Answer 1

First of all, the table you have is not a match with the DFA.

The pair table method uses the classes of equivalency. First we partition the states in two: final and non-final states. Initially every final state is distinguishable from any non-final state. So you should create a table like below and mark (q0,q1) and (q1,q2) as q1 is final but q0 and q2 are non-final states.

+----+ | q0 | +----+----+ | q1 | x | +----+----+----+ | q2 | | x | +----+----+----+----+ | q0 | q1 | q2 | +----+----+----+

Then iteratively, you continue marking using the following rule and stop when in an iteration nothing is changed:

Mark (q_i,q_j) if for some alphabet symbol a, is marked. Int above table, and . As (q1,q2) is marked, we should mark (q0,q2) as well. Note that we only have half of the table. Hence, (q0,q2)=(q2,q0).

+----+ | q0 | +----+----+ | q1 | x | +----+----+----+ | q2 | x | x | +----+----+----+----+ | q0 | q1 | q2 | +----+----+----+