# 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=table, which is not marked hence they are combined. – Ritwik Jan 9 '17 at 17:51
{"ft_lang_label":"__label__en","ft_lang_prob":0.8948751,"math_prob":0.98773986,"size":4013,"snap":"2020-24-2020-29","text_gpt3_token_len":1152,"char_repetition_ratio":0.13544525,"word_repetition_ratio":0.050397877,"special_character_ratio":0.3035136,"punctuation_ratio":0.123582765,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99353105,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,3,null,3,null,3,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-14T03:08:02Z\",\"WARC-Record-ID\":\"<urn:uuid:5dc685cd-7d52-41d2-a16d-3cfcec3f1a56>\",\"Content-Length\":\"149910\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3b751849-5e89-437d-80e0-c554d8d7a02a>\",\"WARC-Concurrent-To\":\"<urn:uuid:e50d24aa-12e5-467b-919e-ead420c9c519>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/68464/how-to-prove-q1-and-q2-are-equal-using-state-equivalence-algorithm\",\"WARC-Payload-Digest\":\"sha1:3HED3CJAQ6XZN4G7V7XHH24HPWLS7WYI\",\"WARC-Block-Digest\":\"sha1:ESMJIXX3MCESLGHLITRDMY5SA6FZC6C2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593657147917.99_warc_CC-MAIN-20200714020904-20200714050904-00040.warc.gz\"}"}