首先，这不是要求将NFA转换为DFA的算法的问题。
众所周知(并证明)，NFA的等效DFA最多具有2n个状态，即使在大多数情况下，其NFA的状态数或多或少都与NFA相同。
我如何预测与NFA等效的DFA的州数估算值？哪种特定类型的NFA需要等效的DFA具有2n个状态？
我问这个问题的原因是能够“发明”一些肯定会产生的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/