3
$\begingroup$

So I wrote an implementation of Hopcroft's algorithm. While testing, I discovered that it would sometimes produce an automaton that wasn't equivalent to the original. At first, I figured it must be a bug in my code, but after going over the algorithm by hand with a small example, it seems to be a bug in my understanding of the algorithm. Can someone help me correct my understanding?

Here is the algorithm, copied from the paper "Re-describing and algorithm by Hopcroft" by Knuutila. (This version differs a little from the one on Wikipedia, but I have essentially the same problem with that one too.)

let P = {F, F^c}, where F is the set of accepting states
let W = {(F, x) for every x in the alphabet}
while W is non-empty:
    remove an arbitrary element (A, x) from W
    let X be the set of states that move into A on input x
    for every Y in P that intersects non-trivially with X:
        replace Y in P by (Y intersect X) and Y \ X
        for every symbol x:
            if (Y, x) in W:
                replace (Y, x) in W by (Y intersect X, x) and (Y \ X, x)
            else
                add either (Y intersect X, x) or (Y \ X, x) to W
return P

Note that there are two sources of non-determinism in this algorithm: we can remove an arbitrary element from W, and if (Y, x) is not in W then we have a choice as to whether to add (Y intersect X, x) or (Y \ X, x). Unless I have misunderstood something, the algorithm is supposed to be correct no matter what choices we make.

Now, here is my example:

example DFA

The alphabet is {a, b, c} and the only accepting state is 4, so we start the algorithm with P = 0123|4 and W = {(4, a), (4, b), (4, c)}.

In the first round, suppose we choose (4, b) as our arbitrary element of W. Nothing moves to 4 on input b, so the inner loop is empty. We get back to the outer loop with P=0123|4 and W = {(4, a), (4, c)}.

Next, suppose we choose (4, c). Then X = 12, which intersects non-trivially with 0123, splitting it into 03|12. Since no (0123, x) belongs to W, the "if" condition always fails. Suppose that we add (12, a), (12, b) and (12, c) into W. We get back to the outer loop with P=03|12|4 and W = {(4, a), (12, a), (12, b), (12, c)}.

Next, suppose we choose (4, a). Then X = 3, which intersects non-trivially with 03, splitting it into 0|3. Since so (03, x) belongs to W, the "if" condition always fails. Suppose that we add (0, a), (0, b) and (0, c) into W. We get back to the outer loop with P=0|12|3|4 and W = {(12, a), (12, b), (12, c), (0, a), (0, b), (0, c)}.

All of the rest of the main loop iterations leave P alone, since 0 is the only state that leads into any of 0, 1, or 2. So we end up returning 0|12|3|4. This is clearly wrong, though, because the string "aa" is an accepting input for state 1 but not state 2, so states 1 and 2 are not equivalent.

$\endgroup$
  • $\begingroup$ If there's an accessible link to the paper, could you provide it? $\endgroup$ – Rick Decker Sep 11 '15 at 0:16
  • $\begingroup$ @RickDecker Wikipedia and Paper. The lemma on wiki references Corollary 10 in the paper. I am checking it. $\endgroup$ – Terence Hang Sep 11 '15 at 4:05
3
$\begingroup$

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function).

For incomplete DFA with partial state transition function $\delta$. You can always convert it to complete DFA $M'=\{Q',\Sigma,\delta',q_0,F\}$ where $$Q'=Q\cup\{q_{err}\}$$ and $\delta'$ extends $\delta$ by define $\delta_a(q)=q_{err}$ for all undefined $\delta_a(q), \delta_a\in\delta,q\in Q\cup\{q_{err}\}$.

$\endgroup$
  • $\begingroup$ Thanks, that was what I was missing! If I add 5 as my error state then after step 2 I have the partition 035|12|4 and after step 3 I have the partition 05|12|3|4. Then adding either 05 or 3 to W will result in splitting 12. $\endgroup$ – Joe Neeman Sep 11 '15 at 9:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.