当我从正则表达式创建NFA时，我在“描述每个步骤”方面遇到了问题。问题如下：
将以下正则表达式转换为非确定有限状态自动机（NFA），清楚地描述您使用的算法的步骤： (b|a)*b(a|b)
我已经制作了一个简单的三状态机，但这很大程度上是基于直觉。 这是我的讲师过去考试的问题，他还写了有关汤普森算法的以下解释：http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html
是否有人能够澄清如何“清楚地描述每个步骤”？它似乎只是一组基本规则，而不是要遵循的步骤算法。
也许我错过了某个算法，但到目前为止，我只是根据猜测创建它们。
一般方法的简短版本。
有一个名为Thompson-McNaughton-Yamada构造算法的算法，有时只称为“Thompson Construction”。在沿途填充各个部分的同时，遵守运算符优先级构建中间NFA：首先是括号，然后是Kleene星号（例如，a*），然后是连接（例如，ab），最后是交替（例如，a|b）。
以下是构建（b|a）*b（a|b）的NFA的详细步骤：
构建顶层
处理括号。注意：在实际实现中，通过对其内容进行递归调用来处理括号可能是有意义的。为了清晰起见，我将推迟对括号内任何内容的评估。
Kleene星号：只有一个*，因此我们构建一个名为P的占位符Kleene星号机器（稍后将包含b|a）。
中间结果：
连接：将P附加到b，并将b附加到称为Q的占位符机器上（其中将包含（a|b）。中间结果：
没有括号外的替代，因此我们跳过它。
现在我们有一个P*bQ机器。（请注意，我们的占位符P和Q只是连接机器。）我们通过递归应用上述步骤，用b|a的NFA替换P边缘，并用a|b的NFA替换Q边缘。
构建 P
跳过。没有括号。
跳过。没有 Kleene 星号。
跳过。没有连接符。
为 b|a 构建交替机器。中间结果：
整合 P
接下来，我们回到那台 P*bQ 机器并拆除 P 边缘。我们让 P 边缘的源 作为 P 机器的起始状态，而 P 边缘的目的地 则作为 P 机器的目标状态。我们还使该状态拒绝（取消其成为接受状态的属性）。结果如下所示：
构建Q
跳过，没有括号。
跳过，没有Kleene星号。
跳过，没有连接操作符。
为a|b构建交替机器。顺便说一下，交替操作是可交换的，因此a|b在逻辑上等价于b|a。（阅读：由于懒惰而跳过此次注释中的图表。）
整合 Q
我们做的与上面 P 相同，只是用我们构建的中间 b|a 机器替换了 Q 边缘。这是结果：
塔达！呃，我的意思是，证毕。
想了解更多吗？
上面的所有图像都是使用在线工具自动生成正则表达式到非确定性有限状态自动机生成的。您可以在网上找到其Thompson-McNaughton-Yamada构造算法的源代码。
该算法也在Aho的编译器原理、技术和工具中提到，尽管其实现细节很少。您还可以从优秀的Russ Cox的C语言中的Thompson构建实现中学习，他在一篇关于正则表达式匹配的流行文章中详细描述了它。
