RE 到 NFA Thompson 的构造步骤 ((c|a)b*)*
RE to NFA Thompson's construction steps ((c|a)b*)*
我试图通过使用 thompsom 的构造将 ((c|a)b*)* 转换为 nfa，但我理解了一些错误，因为结果不是它应该的结果。如果您能指出我的错误，我将非常高兴。
汤普森的构造规则：
- 1)每个NFA都有一个开始状态和一个接受状态。
- 2)除起始状态外，不允许任何转换进入起始状态。
- 3)没有转换从接受状态退出。
- 4)一个ε-transition总是连接2个状态，这些状态曾经是一些REs的开始或接受状态
- 5)一个状态最多可以有 2 个传入和 2 个退出 ε-transitions
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 需要它，这对我来说是有意义的。所以我想我在连接过程中犯了一个错误。提前谢谢你。
我试图通过使用 thompsom 的构造将 ((c|a)b*)* 转换为 nfa，但我理解了一些错误，因为结果不是它应该的结果。如果您能指出我的错误，我将非常高兴。 汤普森的构造规则：
- 1)每个NFA都有一个开始状态和一个接受状态。
- 2)除起始状态外，不允许任何转换进入起始状态。
- 3)没有转换从接受状态退出。
- 4)一个ε-transition总是连接2个状态，这些状态曾经是一些REs的开始或接受状态
- 5)一个状态最多可以有 2 个传入和 2 个退出 ε-transitions
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 需要它，这对我来说是有意义的。所以我想我在连接过程中犯了一个错误。提前谢谢你。
