dfa - 用于将 NFA 转换为 DFA 的伪代码

正如标题所暗示的，我希望有人帮助我编码 NFA 到 DFA 的转换。我只需要伪代码。我尝试使用谷歌搜索，我什至找到了整个源代码，但是几乎没有资源可以帮助我为我提供正式的转换方法(用书面文字，而不是通过图片)。这是一个家庭作业问题，我已经过了截止日期，所以我真的需要一些利他主义。

谢谢。

最佳答案

我写了一篇关于这个主题的文章。

Converting a NFA to a DFA by subset construction

它还包括有关如何进行转换的伪代码。

基本上算法是，从 NFA 的起始状态开始:

Perform closure on the current state set
For each input symbol do the GOTO operation on the closure set.
   If the state set you get from the GOTO is not empty
      Do a closure of the state set.
      If it is a new set of states:
         add a transition between the state sets on the input
         repeat the entire operation on this new set
      Else
         add a transition between the state sets on the input

这样做直到没有更多的集合或过渡添加。这是一个难以解释的算法，但如果您完成了 CLOSURE 和 GOTO 两个基本操作，则不是很难。

关于dfa - 用于将 NFA 转换为 DFA 的伪代码，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11954935/