theory - 从正则表达式创建 NFA 的步骤

Question

从正则表达式创建 NFA 时，我遇到了“描述每个步骤”的问题。问题如下:

将以下正则表达式转换为非确定性有限状态自动机 (NFA)，清楚地描述您使用的算法的步骤:
(b|a)*b(a|b)

我已经制作了一个简单的三态机器，但它很大程度上来自直觉。
这是我的讲师在过去的考试中写的一个问题，他还写了对汤普森算法的以下解释:http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

谁能弄清楚如何“清楚地描述每个步骤”？它似乎只是一组基本规则，而不是一个需要遵循的步骤的算法。

也许有一种算法我已经在某处掩盖了，但到目前为止，我只是用有根据的猜测创建了它们。

Answer 1

一般方法的简短版本。
有一种算法称为 Thompson-McNaughton-Yamada 构造算法，有时也称为“Thompson 构造”。一个构建中间 NFA，沿途填充片段，同时尊重运算符优先级:首先是括号，然后是 Kleene Star(例如，a*)，然后是串联(例如，ab)，然后是交替(例如，a|b)。

这是构建 (b|a)*b(a|b) 的 NFA 的深入演练

构建顶层

处理括号。注意:在实际实现中，通过对其内容的递归调用来处理括号是有意义的。为了清楚起见，我将推迟评估括号内的任何内容。

Kleene Stars:那里只有一个 *，所以我们构建了一个名为 P 的占位符 Kleene Star 机器(稍后将包含 b|a)。
中间结果:

连接:将 P 附加到 b，并将 b 附加到称为 Q 的占位符机器(将包含 (a|b)。中间结果:

括号外没有交替，所以我们跳过它。

现在我们坐在 P*bQ 机器上。 (请注意，我们的占位符 P 和 Q 只是连接机器。)我们将 p 边替换为 b|a 的 NFA，并通过上述步骤的递归应用将 Q 边替换为 a|b 的 NFA。

P楼

跳过。没有括号。

跳过。没有克莱恩明星。

跳过。没有污染。

为 b|a 构建交替机器。中间结果:

积分 P

接下来，我们回到那个 P*bQ 机器，我们撕掉 P 边。我们将 P 边的源作为 P 机器的起始状态，将 P 边的目的地作为 P 机器的目标状态。我们还使该状态拒绝(取消其作为接受状态的属性)。结果如下所示:


Q楼

跳过。没有括号。

跳过。没有克莱恩明星。

跳过。没有污染。

为 a|b 构建交替机器。顺便说一句，交替是可交换的，所以 a|b 在逻辑上等价于 b|a。 (阅读:出于懒惰而跳过这个小脚注图。)

积分 Q

除了用我们构建的中间 b|a 机器替换 Q 边缘之外，我们做了上面对 P 所做的事情。这是结果:


多田!呃，我的意思是，QED。

想知道更多？

以上所有图片均使用 an online tool for automatically converting regular expressions to non-deterministic finite automata 生成.你可以找到它的 source code for the Thompson-McNaughton-Yamada Construction algorithm在线的。

该算法也在 Aho's Compilers: Principles, Techniques, and Tools 中得到解决。 ，尽管它对实现细节的解释很少。您也可以向 an implementation of the Thompson Construction in C 学习由优秀的 Russ Cox 撰写，他在一篇关于 regular expression matching 的热门文章中对其进行了详细描述.