1
$\begingroup$

enter image description here

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

$\endgroup$
  • $\begingroup$ You are not applying it correctly. When I apply it it merges q1 and q2. Try to follow the instructions more closely. $\endgroup$ – Yuval Filmus Jan 9 '17 at 15:52
  • $\begingroup$ @YuvalFilmus that is exactly what I am asking . Where Im I going wrong ? I too know that q1 and q2 are equal. $\endgroup$ – user63554 Jan 9 '17 at 17:31
  • $\begingroup$ You are just not following the steps as written. When I ran the same algorithm, it came up properly. $\endgroup$ – Yuval Filmus Jan 9 '17 at 17:41
  • $\begingroup$ Could you pls point out where am I going wrong ? Im still not able to figure out myself $\endgroup$ – user63554 Jan 9 '17 at 17:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 9 '17 at 17:49
1
$\begingroup$

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 sample 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]

min DFA

In your example:
0 equivalent partitions: [q1 q2]
1 equivalent partitions: [q1 q2]

Hence they are combined.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user63554 Jan 9 '17 at 17:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Ritwik Jan 9 '17 at 17:51
  • $\begingroup$ This makes more sense to me . Does the table filling algorithm same as State equivalence algorithm ? $\endgroup$ – user63554 Jan 9 '17 at 17:53
  • $\begingroup$ 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. $\endgroup$ – Ritwik Jan 9 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy