DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA's-Automata

Sample DFA:

You can use following simplification assumptions to make the required input task relatively simple:

· States are numbered consecutively starting from 1 and state 1 is the Initial State.

· Likewise input symbols are each one character long and are consecutively ordered such as 0, 1, 2, 3, … or a, b, c, d, ...

· A DFA may have one or more number of states and zero or more number of Final states.

Under these simplifying assumptions, our sample DFA can be completely specified by the following input frame: (Note comments are NOT parts of inputs)

· 7 // total number of states

· 4 // total number of Final states

· 2 // two input symbols, 0 and 1 in that order

· 1 2 3 4 // these are four Final states. So, the other three states are non-final.

· 1 2 // two transitions of state 0, Q0

· 3 4 // two transitions of state 1, Q1

· 5 5 // two transitions of state 2, Q2

· 3 4

· 5 5

· 6 5

· 6 6 // two transitions of the last state, Q6

Illustration.

Sample DFA: We consider the following DFA with seven states and two input symbols where Q1, Q2, Q3 and Q4 are final.

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:

1. 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)

2. 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.

3. 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:

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

5. Iteration-2

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

6. 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). So, two states q1 and q3 can be combined into one, another two states q2 and q4 can be combined into one and finally two states q5 and q6 can also be combined into one. So, this DFA will have four states in all which is the minimal number of necessary states for this DFA.

Note that the initial state q0 is not indistinguishable from any state, namely, it is not equivalent to any state we have or it is different from every other state.