Hopcroft Minimization Issues

Question

I'm implementing Hopcroft DFA minimization from the below wikipedia page and something's going wrong. It looks like W is getting an empty set added every loop and when I prevent the empty set from getting added the results look wacky:

Starting DFA:

8
Sigma:     a     b     c
------------------------
    0:     1     2     3
    1:     1     4     5
    2:     4     2     6
    3:     5     6     3
    4:     4     4     7
    5:     5     7     5
    6:     7     6     6
    7:     7     7     7
------------------------
0: Initial State
0,1,2,3,4,5,6: Accepting State(s)

Output:

[7]
[0, 1, 2, 4]
[0, 1, 3, 5]
[1, 4, 5]
[0, 2, 3, 6]
[2, 4, 6]
[3, 5, 6]

https://en.wikipedia.org/wiki/DFA_minimization

Here's my actual hopcroft code:

public Set<Set<Integer>> hopcroftMinimization() {
  Set<Set<Integer>> P = new HashSet<>();
  Set<Set<Integer>> W = new HashSet<>();
  P.add(new HashSet<Integer>(accepting));
  P.add(setSubtraction(states, accepting));
  W.addAll(P);
 
  while (!W.isEmpty()) {
    System.out.println(W.toString());
    Object[] wArr = W.toArray();
    Object[] pArr = P.toArray();
 
    for (Object A : wArr) {
      W.remove(A);
      System.out.println(W.toString());
      for (char input : validInputs) {
        Set<Integer> X = findX((Set)A, input);
 
        for (Object Y : pArr) {
          Set<Integer> xAndY = intersection(X, (Set)Y);
          Set<Integer> yNotX = setSubtraction((Set)Y, X);
          if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
            P.remove(Y);
            P.add(xAndY);
            P.add(yNotX);
            if (W.contains(Y)) {
              W.remove(Y);
              W.add(xAndY);
              W.add(yNotX);
            }
          } else {
            if (xAndY.size() <= yNotX.size()) {
              W.add(xAndY);
            } else {
              W.add(yNotX);
            }
          }
        }
      }
      
    }
  }
 
  return P;
}

Here's a pastebin with the full class: https://pastebin.com/kYyYbCXU

Answer 1

This else is in the wrong place:

    for (Object Y : pArr) {
      Set<Integer> xAndY = intersection(X, (Set)Y);
      Set<Integer> yNotX = setSubtraction((Set)Y, X);
      if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
        P.remove(Y);
        P.add(xAndY);
        P.add(yNotX);
        if (W.contains(Y)) {
          W.remove(Y);
          W.add(xAndY);
          W.add(yNotX);
        }
      ///////////////////////////
      } else { // <<<--- THIS BLOCK
        if (xAndY.size() <= yNotX.size()) {
          W.add(xAndY);
        } else {
          W.add(yNotX);
        }
      }
      ///////////////////////////
    }

It should be here:

    for (Object Y : pArr) {
      Set<Integer> xAndY = intersection(X, (Set)Y);
      Set<Integer> yNotX = setSubtraction((Set)Y, X);
      if (!xAndY.isEmpty() && !yNotX.isEmpty()) {
        P.remove(Y);
        P.add(xAndY);
        P.add(yNotX);
        if (W.contains(Y)) {
          W.remove(Y);
          W.add(xAndY);
          W.add(yNotX);
        ///////////////////////////
        } else { // <<<--- THIS BLOCK
          if (xAndY.size() <= yNotX.size()) {
            W.add(xAndY);
          } else {
            W.add(yNotX);
          }
        }
        ///////////////////////////
      } 
    }

Not sure whether that's the only issue, but at least it's an issue.