computer-science - NFA 到 DFA 的问题

Question

首先，这不是要求算法将 NFA 转换为 DFA 的问题。

众所周知(并证明)NFA 的等效 DFA 最多具有 2n 个状态，尽管大多数情况下它或多或少具有与 NFA 相同的状态数。

我如何预测 NFA 等效 DFA 将具有的状态数的估计值？哪种特定类型的 NFA 需要等效的 DFA 才能具有 2n 个状态？

我提出这个问题的原因是能够“发明”一些 NFA，这些 NFA 肯定会在不考虑最小化的情况下产生 2n - 1 个状态加上“死状态”。

Answer 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 状态，它就会变得更加棘手。