非最小 DFA 的性能特征
Performance characteristics of a non-minimal DFA
关于最小化 DFA 的算法的性能已经写了很多。这让我的 Google-fu 很沮丧，因为那不是我要找的东西。
关于非最小化 DFA 的性能特征，我们能概括地说一下吗？我的直觉是，相对于输入的长度，非最小 DFA 的 运行 时间仍然是 O(n)。似乎最小化只会影响状态的数量，从而影响存储需求。这是正确的吗？
如果我们对派生 DFA 的 NFA 的构造有所了解，我们是否可以改进概括？例如，假设 NFA 完全是通过对匹配一个输入符号或 epsilon 的原始自动机应用串联、并集和 Kleene 星形运算来构建的。由于无法删除转换或创建任意转换，我认为不可能有任何死状态。我们可以对从这些 NFA 构造的 DFA 进行哪些概括？我对理论和经验答案都很感兴趣。
输入接受的"runtime"的推理是一样的，因为通常会消耗输入的一个字符；在 DFA 的上下文中，我从未听说过 "runtime"（在渐近运行时复杂性的意义上）的概念。最小化旨在最小化 DFA 的状态数（即优化"implementation size"）。
关于你的第一个问题，在非最优DFA的运行时间。纯粹从理论上讲，您的直觉认为它在 O(n) 中仍然 运行 是正确的。但是，想象一下（作为示例）Kleene-Star 运算符的以下伪代码：
// given that the kleene-star operator starts at i=something
while string[i] == 'r':
accepting = true;
i++;
while string[i] == 'r':
accepting = true;
i++;
// here the testing of the input string can continue for i+1
如您所见，前两个while循环是相同的，可以理解为冗余状态。但是，"splitting" while 循环会降低（除其他外）您的分支预测准确性，因此会降低总体 运行 时间（有关更多详细信息，请参阅 Mysticial 对分支预测的精彩解释 here。
许多其他类似的 "practical" 论点可以解释为什么非最佳 DFA 会变慢；其中，正如您提到的，内存使用率更高（在许多情况下，更多内存意味着速度更慢，因为相比之下，内存是计算机中速度较慢的部分）；更多 "ifs"，对于每个额外的状态，都需要对其后续状态进行输入检查；可能有更多循环（如示例中所示），这不仅会在分支预测的基础上使算法变慢，而且仅仅是因为某些编程语言在循环上非常慢。
关于你的第二个问题——我不确定你的意思。毕竟，如果你正确地进行了转换，你应该首先推导出一个非常优化的 DFA。
编辑：
在讨论中提出了一个想法，即可以从一个 NFA 构造多个非最小 DFA，它们具有不同的效率（无论选择何种度量），不是在实现中，而是在 DFA 的结构中。
这是不可能的，因为只有一个最佳 DFA。这是证明的概要：
- 假设我们创建和最小化 DFA 的过程是最优的。
- 在应用程序时，我们先从构造一个DFA开始。在这一步中，我们可以创建无限多个等价状态。这些状态都以某种方式连接到 NFA 的图表。
- 在下一步中，我们将消除所有不可到达的状态。这与性能无关，因为无法到达的状态对应于 "dead code" - 永远不会被执行。
- 在第四步中，我们通过对等效状态进行分组来最小化 DFA。这就是它变得有趣的地方——因为我们可以用不同的方式做到这一点，从而产生具有不同性能的不同 DFA。但是，我们唯一的 "choice" 是将状态分配给不同的组。
因此，为了争论起见，我们假设我们可以做到这一点。
但是，根据最小化算法背后的思想，我们只能对等价状态进行分组。因此，如果我们有不同的选择来对特定状态进行分组，通过等价的传递性，不仅状态将等价于两个组，而且组也将是等价的。所以如果我们能以不同的方式分组，算法就不会是最优的，因为它会首先将组中的所有状态分组到一个组中。
因此，假设可以有不同的最小化一定是错误的。
关于最小化 DFA 的算法的性能已经写了很多。这让我的 Google-fu 很沮丧，因为那不是我要找的东西。
关于非最小化 DFA 的性能特征，我们能概括地说一下吗？我的直觉是，相对于输入的长度，非最小 DFA 的 运行 时间仍然是 O(n)。似乎最小化只会影响状态的数量，从而影响存储需求。这是正确的吗？
如果我们对派生 DFA 的 NFA 的构造有所了解，我们是否可以改进概括？例如，假设 NFA 完全是通过对匹配一个输入符号或 epsilon 的原始自动机应用串联、并集和 Kleene 星形运算来构建的。由于无法删除转换或创建任意转换，我认为不可能有任何死状态。我们可以对从这些 NFA 构造的 DFA 进行哪些概括？我对理论和经验答案都很感兴趣。
输入接受的"runtime"的推理是一样的，因为通常会消耗输入的一个字符；在 DFA 的上下文中，我从未听说过 "runtime"（在渐近运行时复杂性的意义上）的概念。最小化旨在最小化 DFA 的状态数（即优化"implementation size"）。
关于你的第一个问题，在非最优DFA的运行时间。纯粹从理论上讲，您的直觉认为它在 O(n) 中仍然 运行 是正确的。但是，想象一下（作为示例）Kleene-Star 运算符的以下伪代码：
// given that the kleene-star operator starts at i=something
while string[i] == 'r':
accepting = true;
i++;
while string[i] == 'r':
accepting = true;
i++;
// here the testing of the input string can continue for i+1
如您所见，前两个while循环是相同的，可以理解为冗余状态。但是，"splitting" while 循环会降低（除其他外）您的分支预测准确性，因此会降低总体 运行 时间（有关更多详细信息，请参阅 Mysticial 对分支预测的精彩解释 here。
许多其他类似的 "practical" 论点可以解释为什么非最佳 DFA 会变慢；其中，正如您提到的，内存使用率更高（在许多情况下，更多内存意味着速度更慢，因为相比之下，内存是计算机中速度较慢的部分）；更多 "ifs"，对于每个额外的状态，都需要对其后续状态进行输入检查；可能有更多循环（如示例中所示），这不仅会在分支预测的基础上使算法变慢，而且仅仅是因为某些编程语言在循环上非常慢。
关于你的第二个问题——我不确定你的意思。毕竟，如果你正确地进行了转换，你应该首先推导出一个非常优化的 DFA。
编辑： 在讨论中提出了一个想法，即可以从一个 NFA 构造多个非最小 DFA，它们具有不同的效率（无论选择何种度量），不是在实现中，而是在 DFA 的结构中。 这是不可能的，因为只有一个最佳 DFA。这是证明的概要：
- 假设我们创建和最小化 DFA 的过程是最优的。
- 在应用程序时，我们先从构造一个DFA开始。在这一步中，我们可以创建无限多个等价状态。这些状态都以某种方式连接到 NFA 的图表。
- 在下一步中，我们将消除所有不可到达的状态。这与性能无关，因为无法到达的状态对应于 "dead code" - 永远不会被执行。
- 在第四步中，我们通过对等效状态进行分组来最小化 DFA。这就是它变得有趣的地方——因为我们可以用不同的方式做到这一点，从而产生具有不同性能的不同 DFA。但是，我们唯一的 "choice" 是将状态分配给不同的组。 因此，为了争论起见，我们假设我们可以做到这一点。 但是，根据最小化算法背后的思想，我们只能对等价状态进行分组。因此，如果我们有不同的选择来对特定状态进行分组，通过等价的传递性，不仅状态将等价于两个组，而且组也将是等价的。所以如果我们能以不同的方式分组，算法就不会是最优的，因为它会首先将组中的所有状态分组到一个组中。 因此，假设可以有不同的最小化一定是错误的。