# How to prove Q1 and Q2 are equal using state equivalence algorithm

I was applying state equivalence algorithm in this diagram. On input a and b Q1 and Q2 are going to different states. Which implies the states are not equal according to the state equivalence algorithm. But they are equal and we knows that , right ? Where am I going wrong ? Please help me how to prove these state are equal using state equivalence algorithm

• You are not applying it correctly. When I apply it it merges q1 and q2. Try to follow the instructions more closely. – Yuval Filmus Jan 9 '17 at 15:52
• @YuvalFilmus that is exactly what I am asking . Where Im I going wrong ? I too know that q1 and q2 are equal. – user63554 Jan 9 '17 at 17:31
• You are just not following the steps as written. When I ran the same algorithm, it came up properly. – Yuval Filmus Jan 9 '17 at 17:41
• Could you pls point out where am I going wrong ? Im still not able to figure out myself – user63554 Jan 9 '17 at 17:44
• I suspect you are not following the algorithm in your link, but some other algorithm. I suggest taking a few hours to read carefully the algorithm in this link and execute it as written. – Yuval Filmus Jan 9 '17 at 17:49

The algorithm is working fine on this DFA. At step 2 you'll get the table as:

  1 2
1 G G
2   G


G is green.

If there is an unmarked pair (Qi, Qj), mark it if the pair {δ(Qi, A), δ (Qj, A)} is marked for some input alphabet. Where A is set of all inputs.

{δ(1, 'a'), δ(2, 'a')} = {2,1} = {1,2}
{δ(1, 'b'), δ(2, 'b')} = {1,2}

{1,2} or {2,1} is not marked. Hence move to step 4, Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

I prefer the method of partitioning for minimizing the DFA. Consider the following DFA
State transition table for the DFA will be:

   0  1
a  b  c
b  a  d
c  e  f
d  e  f
e  e  f
f  f  f


Draw 0 equivalent partitions, by separating final and non-final states in different sets.
[a b f] [c d e]
Draw 1 equivalent partitions, by taking every possible pair from each set and checking whether their transitions on an input symbol belongs to a single set or not. For example {a,b} on 0 goes to {a,b} and it belongs to a single set [a b f], {a,b} on 1 goes to {c,d} which belongs to 1 single set [c d e], hence {a,b} are 1 equivalent. But {a,f} on 1 goes to {c,f} and it doesn't belong to a single set, hence they are not equivalent. So separate them. (you can check for {b,f},{c,d},{c,e},{d,e} as well, result will be the same)
[a b] [f] [c d e]
Draw 2 equivalent partitions, by repeating the procedure and you'll find nothing is changed. Hence final configuration is reached. Merge [a b] and [c d e]

0 equivalent partitions: [q1 q2]
1 equivalent partitions: [q1 q2]
• if you are talking about SE algorithm then yes, on a q1-->q2 and q2-->q1, when combined we can say, on a {q1,q2} ---> {q2,q1}. The purpose of filling the upper triangle with Green color is to signify that it is same as lower triangle so there is no point in calculating it again. Therefore {q2,q1} = {q1,q2}; simply put table[2][1]=table[1][2], which is not marked hence they are combined. – Ritwik Jan 9 '17 at 17:51