regex - RE 到 NFA Thompson 的构造步骤 ((c|a)b*)*

Question

我试图通过使用 thompsom 的构造将 ((c|a)b*)* 转换为 nfa，但我理解了一些错误，因为结果不是它应该的结果。如果您能指出我的错误，我将非常高兴。汤普森的构造规则:

• 1) 每个 NFA 都有一个开始状态和一个接受状态。
• 2)除了起始转换外，不允许任何转换进入起始状态。
• 3) 没有过渡从接受状态退出。
• 4)一个ε-transition总是连接2个状态，这些状态曾经是一些REs的开始或接受状态
• 5) 一个状态最多可以有 2 个传入和 2 个退出 ε 转换

• 6)对于所用字母数字的特定字符，一个状态最多可以有 1 个传入和 1 个退出转换。

  第 1 步:我为每个角色创建了 NFA

第 2 步:括号优先，所以我创建了 c|a

第 3 步:然后我创建了 b*

第 4 步:然后我组合 c|a 和 b* 来创建 (c|a)b*

第 5 步:最后我创建了 ((c|a)b*)*

与正确解决方案的不同之处在于，在最后一个 nfa 中(示例没有显示步骤，最后状态重新编号)没有 s9。所以 S8 ε-transists 到 S5 和 S5 ε-transists 到 S10。如果 b* 没有 S9 状态但由于规则 2 需要它，这对我来说是有意义的。所以我想我在连接过程中犯了一个错误。提前谢谢你。

Answer 1

规则 2 说任何东西都不能进入 S11，这里不相关。连接时(第 4 步)，S8 和 S9 应该已经合并。

来自维基百科，

The concatenation expression st is converted to