将RE转换为NFA

Question

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

Answer 1

他们都是正确的，因为你说。

第一个看起来像是使用一套标准规则生成的 - 在这种情况下，它是过度杀伤（而且看起来很傻），但在更复杂的情况下，遵循简单的规则比保存整个事物更容易在你的脑海中，从头开始编写相应的NFA。一般来说，NFA可以被重写，使其具有单一的最终状态（显然已经只有一个起始状态）。

然后，可以将这种形式的两个NFA组合起来，使得它们组合时所接受的语言是它们单独接受的语言的联合 - 这对应于正则表达式中的或（+）。为了以这种方式组合NFA，只需创建一个新节点作为起始状态，并将它与ε转换连接到两个NFA的开始状态。我们创建了一个额外的节点来作为统一的最终状态，并且为了使NFA在单个最终状态下完整地结束（这样我们可以使用这个NFA递归地用于其他工会，如果我们想要的话）将旧的最终状态（即失去其最终状态）连接到它。

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

Answer 2

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

Thompson的构造算法使用NFA与电子移动从任何正则表达式构建自动机。它提供了一个标准的方法来构建一个自动机从正则表达式时，它可以方便地自动化施工。