如果在使用 Hop-croft 算法最小化确定性有限自动机中接受所有状态怎么办？
What if all states are accepted in Minimizing Deterministic Finite Automata with Hop-croft Algorithm?
这里有一个像这样的 DFA：
这是否已经是最小化的 DFA，或者我们是否应该使用 Hopcroft 算法将所有接受的状态分组为一个 class 并输出：
来最小化它
Hopcroft 最小化算法假设一个完整 DFA，其中每个状态在字母表中的每个符号上都有一个转换。
使用不完整的 DFA 很常见，其中允许缺少转换。从技术上讲，这是一个 NFA（尽管它是完全确定的）。与 DFA 不同，NFA 允许字母表符号从给定状态生成 集合 可能的转换，并且该集合可能为空，在这种情况下 NFA 停止。 （DFA 仅在到达输入末尾时停止。）
为了最小化的目的，通常添加一个非接受 "sink" 状态，它在每个输入符号上都有一个到自身的转换。然后所有 "missing" 转换都可以替换为到接收器状态的转换，从而使自动机完成。 （当然，在实践中，人们更愿意使用在无效输入时立即停止的自动机，而不是在输入结束之前在汇状态中无用地旋转。在最小化之后，汇状态可以被移除。）
根据该约定，您的 DFA 不仅有接受状态；还有接受状态。有一个（隐含的）非接受状态。如果 DFA 真的只有接受状态，那么它会识别 Σ* 并且确实可以最小化为单个接受状态。
Hopcroft 算法的运行时间为 O(sN log N)，其中 s 是字母表的大小，N 是状态数。由于假设 DFA 是完整的，sn 也是自动机图中的边数（每个状态必须有 s 转换），因此我们可以将其写为 O(E log N)。但是如果我们放宽 DFA 是完整的要求，它的图可能会有相当少的边，尽管只是一个常数因子（如果我们将字母表大小设为常数）。已经有几种算法提议试图利用这一事实。例如，参见 Marie-Pierre Béal、Maxime Crochemore。最小化不完全自动机。有限状态方法
和自然语言处理 (FSMNLP'08)，2008 年，美国。 pp.9-16, 2008, 联合研究
中心。
这里有一个像这样的 DFA：
这是否已经是最小化的 DFA，或者我们是否应该使用 Hopcroft 算法将所有接受的状态分组为一个 class 并输出：
来最小化它Hopcroft 最小化算法假设一个完整 DFA，其中每个状态在字母表中的每个符号上都有一个转换。
使用不完整的 DFA 很常见，其中允许缺少转换。从技术上讲，这是一个 NFA（尽管它是完全确定的）。与 DFA 不同，NFA 允许字母表符号从给定状态生成 集合 可能的转换，并且该集合可能为空，在这种情况下 NFA 停止。 （DFA 仅在到达输入末尾时停止。）
为了最小化的目的，通常添加一个非接受 "sink" 状态，它在每个输入符号上都有一个到自身的转换。然后所有 "missing" 转换都可以替换为到接收器状态的转换，从而使自动机完成。 （当然，在实践中，人们更愿意使用在无效输入时立即停止的自动机，而不是在输入结束之前在汇状态中无用地旋转。在最小化之后，汇状态可以被移除。）
根据该约定，您的 DFA 不仅有接受状态；还有接受状态。有一个（隐含的）非接受状态。如果 DFA 真的只有接受状态，那么它会识别 Σ* 并且确实可以最小化为单个接受状态。
Hopcroft 算法的运行时间为 O(sN log N)，其中 s 是字母表的大小，N 是状态数。由于假设 DFA 是完整的，sn 也是自动机图中的边数（每个状态必须有 s 转换），因此我们可以将其写为 O(E log N)。但是如果我们放宽 DFA 是完整的要求，它的图可能会有相当少的边，尽管只是一个常数因子（如果我们将字母表大小设为常数）。已经有几种算法提议试图利用这一事实。例如，参见 Marie-Pierre Béal、Maxime Crochemore。最小化不完全自动机。有限状态方法
和自然语言处理 (FSMNLP'08)，2008 年，美国。 pp.9-16, 2008, 联合研究
中心。