Write a program to implement the "Mark" procedure to minimize the number of states. For details, see the attached assignment file.

Deterministic State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible number of states.

Luckily, there are some simple and efficient procedures to reduce/minimize the number of states in a DFA such as methods "Mark" and "Reduce" on pages 67 and 69 of our textbook.

Task:

Write a program that computes and outputs all equivalent sets of indistinguishable states using the Mark method (page 67) of our textbook.

Illustration.

I find the description of this procedure in our book a little bit confusing. So, I decided to give an illustration on how it is going to work.

Example DFA: We consider the following DFA with seven states and two input symbols where Q_1, Q_2, Q₃ and Q₄ are final.

States/inputs	0	1
Q0	Q1	Q2
Q1	Q3	Q4
Q2	Q5	Q5
Q3	Q3	Q4
Q4	Q5	Q5
Q5	Q6	Q5
Q6	Q6	Q6

Our goal of state minimization can be achieved by an indirect approach. That is, although we need to identify all states that can be treated as the same (indistinguishable or equivalent states) so that they can be combined into just one state, we will instead identify every pair of two states that is just the opposite, namely distinguishable pairs. And, the method Mark is supposed to find all pairs that are distinguishable pairwise.

Since a pair of two states is either distinguishable or indistinguishable, after we find all distinguishable pairs, we are able to identify all indistinguishable pairs from which we can compute all sets of equivalent (indistinguishable) states so that all states in each such set will be combined into a single state thereby reducing/minimizing the total number of necessary states in the DFA.

Steps of Mark:

Initializations:

We will maintain a two-column table, distingPairs, that contains all pairs of distinguishable states found so far.

By definition, every Final state and every NonFinal state are distinguishable as they are obvious different. So, in our example twelve pairs of a Final state and a Nonfinal state are automatically distinguishable. No computations are needed.

So, initially distingPairs will show these twelve pairs as follows: (from now I skip subscripts for state notations)

q0	q1
q0	q2
q0	q3
q0	q4
q5	q1
q5	q2
q5	q3
q5	q4
q6	q1
q6	q2
q6	q3
q6	q4

After this initialization, we iterate computing additional pairs of two distinguishable states, either both Final or both Nonfinal, until no more are found, using two equations (2.5) and (2.6) of page 68.

Iteration-1

We find the following six pairs here:

(q0,q5), (q0,q6), q1,q2), (q1,q4), (q2,q3) and (q3, q4).

Note that in the first pair on input symbol 0 (1) from q0 move is to q1 which is Final while (2) from q5 move is to q6 which is Nonfinal. Also in the second pair on input symbol 0 the next state from q0 is Final while the next state from q6 is Nonfinal and so forth.

So, at the end of Iteration-1, the updated distingPairs will look like:

q0	q1
q0	q2
q0	q3
q0	q4
q5	q1
q5	q2
q5	q3
q5	q4
q6	q1
q6	q2
q6	q3
q6	q4
Q0	Q5
Q0	Q6
Q1	Q2
Q1	Q4
Q2	Q3
Q3	Q4

Since at least one additional distinguishable pair has been found during Iteartion-1, we will go ahead to the Iteration-2

Iteration-2

During this iteration, luckily we find no more distinguishable pair in this case.

We found a total of 18 distinguishable pairs. As there are 21 possible pairs out of seven states we have, there are a total of three indistinguishable pairs:

They are: (q1, q3), (q2, q4) and (q5, q6).

So, this example DFA has four classes of indistinguishable sets of states.

They are (q0), (q1, q3), (q2, q4) and (q5, q6). This is the expected outputs of your program.