nfa - 将 RE 转换为 NFA

Question

哪一种是显示 RE 联合 0+1 的正确方法？我看到了这两种方式，但我认为两者都是正确的。如果两者都是正确的，为什么要把事情复杂化？

Answer 1

正如你所说，它们都是正确的。

第一个看起来像是使用一组标准规则生成的——在这种情况下，它是矫枉过正的（而且看起来很傻），但在更复杂的情况下，遵循简单的规则比把整个事情都记在脑子里更容易从头开始编写等效的 NFA。

通常，可以重写 NFA，使其具有单个最终状态（显然已经只有一个开始状态）。

然后，这种形式的两个 NFA 可以以这样一种方式组合，即它们在组合时接受的语言是它们单独接受的语言的联合——这对应+于正则表达式中的 or ()。要以这种方式组合 NFA，只需创建一个新节点作为起始状态并将其与 ε-transitions 连接到两个 NFA 的起始状态。

然后，为了将 NFA 整齐地结束在单个最终状态（以便我们可以根据需要将此 NFA 递归地用于其他联合），我们创建一个额外的节点作为统一的最终状态并 ε-连接旧的最终状态状态（失去最终状态）。

使用上面的一般规则，很容易得出第一个图（两个 NFA 结合在一起，第一个匹配0，另一个1）——第二个很容易通过常识得出，因为它是一个非常简单的正则表达式 ;-)

Answer 2

第一个构造属于带有 e-moves 的 NFA 类，它是一般 NFA 类的扩展。e-moves 让您无需输入即可进行转换。对于转移函数，重要的是仅使用电子转移来计算从给定状态可到达的状态集。显然，添加 e-moves 并不允许 NFA 接受非常规语言，因此它最终相当于 NFA，然后是 DFA。

Thompson 的构造算法使用带有 e-moves 的 NFA 从任何正则表达式构建自动机。它提供了一种从正则表达式构建自动机的标准方法，可以方便地自动构建。