# 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. Jan 9, 2017 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, 2017 at 17:31
• You are just not following the steps as written. When I ran the same algorithm, it came up properly. Jan 9, 2017 at 17:41
• Could you pls point out where am I going wrong ? Im still not able to figure out myself
– user63554
Jan 9, 2017 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. Jan 9, 2017 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]

Hence they are combined.

• Can u pls show it for the diagram given by me ? actually when I applying the algorithm. On input a q1 is going to q2 and on input a q2 is going q1 . This makes me confused . Had this been going to same states for input then I could have conluded they are equal.
– user63554
Jan 9, 2017 at 17:33
• 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. Jan 9, 2017 at 17:51
• This makes more sense to me . Does the table filling algorithm same as State equivalence algorithm ?
– user63554
Jan 9, 2017 at 17:53
• No no, table filling is Hopcroft's algorithm which is based on Myhill–Nerode equivalence relation. SE algorithm is used in finding equivalent states whereas table filling is used to eliminate nondistinguishable states. Jan 9, 2017 at 18:24