首先，这不是要求算法将 NFA 转换为 DFA 的问题。
众所周知(并证明)NFA 的等效 DFA 最多具有 2n 个状态，尽管大多数情况下它或多或少具有与 NFA 相同的状态数。
我如何预测 NFA 等效 DFA 将具有的状态数的估计值？哪种特定类型的 NFA 需要等效的 DFA 才能具有 2n 个状态？
我提出这个问题的原因是能够“发明”一些 NFA，这些 NFA 肯定会在不考虑最小化的情况下产生 2n - 1 个状态加上“死状态”。
最佳答案
由于不确定性，状态数量激增，这是您问题的关键。
如果您采用 NFA，其中每个转换都是唯一确定的，即确定性 NFA，那么它只不过是一个普通的 DFA。但是，一旦您拥有可以进行两次转换的状态，它就与 DFA 不同。
考虑转换算法，看看如果您有两个或多个具有相同状态标签的转换会发生什么。这是您需要与状态集相对应的那些新状态的地方。
所以问题归结为找出这些超集状态中有多少实际上是可达的。当然，您可以为此发明一种奇特的算法，但要获得正确的数字，只需运行正常的转换算法并删除无法访问的状态即可。
对于具有 n 个状态的 NFA，其等效 DFA 具有 2^n 个状态，请考虑利用非确定性。第一个想法是将所有转换标记为相同，但是，效果不佳。相反，请记住，您需要能够以某种方式到达状态的所有子集，每个子集都有一些标签。
如果不计算起始状态，则可以进行以下构造:创建 n 个节点，并为 2^n 中的每个集合创建一个唯一标签，并在 NFA 中向该集合的每个节点添加带有此标签的转换。这为您提供了具有 n+1 个状态(1 是起始状态)的 NFA，其中 DFA 需要 2^n +1 个状态。当然，一旦你想在最小化后有 2^n 个 DFA 状态，它就会变得更加棘手。
关于computer-science - NFA 到 DFA 的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2021890/