nun*_*nos 9 computer-science finite-automata computation-theory
首先,这不是要求算法将NFA转换为DFA的问题.
众所周知(并且证明)NFA的等效DFA最多有2 n个状态,即使大多数时候它与NFA的状态数或多或少相同.
我如何预测NFA等效DFA所具有的州数量？哪种特定类型的NFA需要等效DFA才能拥有2 n个状态？
我之所以提出这个问题,是因为能够"发明"一些肯定会产生的NFA,而不考虑最小化,2 n - 1个状态加上"死态".
由于非决定论，状态数量呈爆炸式增长，这是你问题的关键。
如果你采用一个 NFA，其中每个转换都是唯一确定的，即确定性 NFA，那么它只不过是一个普通的 DFA。然而，一旦您的状态可能发生两次转换，它就与 DFA 不同。
考虑转换算法，并看看如果一个状态有两个或多个具有相同标签的转换会发生什么。这就是您需要与状态集相对应的新状态的地方。
因此，问题归结为找出这些超集状态中有多少实际上是可以到达的。当然，您可以为此发明一种奇特的算法，但要获得正确的数字，只需运行正常的转换算法并删除无法到达的状态即可。
对于具有 n 个状态的 NFA，而等效的 DFA 有 2^n 个状态，请考虑利用非确定性。第一个想法是将所有转换标记为相同，但是效果不太好。相反，请记住，您需要能够以某种方式到达状态的所有子集，每个子集都有一些标签。
如果不计算起始状态，则可以执行以下构造：创建 n 个节点，并为 2^n 中的每个集合创建一个唯一标签，并在 NFA 中向该集合的每个节点添加带有此标签的转换。这为您提供了具有 n+1 个状态的 NFA（1 是起始状态），其中 DFA 需要 2^n +1 个状态。当然，一旦您想要最小化后有 2^n 个 DFA 状态，事情就会变得更加棘手。