Hopcroft 最小化问题

Question

我正在从下面的维基百科页面实施 Hopcroft DFA 最小化，但出了点问题。看起来 W 在每个循环中都添加了一个空集，当我阻止添加空集时，结果看起来很古怪：

启动 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)

输出：

[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

这是我实际的 hopcroft 代码：

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;
}

这是一个包含完整 class 的 pastebin： https://pastebin.com/kYyYbCXU

Answer 1

这个else放错地方了：

    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);
        }
      }
      ///////////////////////////
    }

应该在这里：

    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);
          }
        }
        ///////////////////////////
      } 
    }

不确定这是否是唯一的问题，但至少是个问题。

Hopcroft 最小化问题

Hopcroft Minimization Issues

java

algorithm

dfa