parsing - 为什么不能简化 NFA 的 Kleene 闭合结构？

Question

大多数来源，例如http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html，建议使用 4 个节点构造 Kleene 闭包。

为什么不能只用2来构造，如下？

Answer 1

为了在连接两个 NFA 时获得正确的结果，您需要确保对于两个组件，或者：

1. 没有结束状态的转换；或者

2. 没有过渡到开始状态。

正常的汤普森结构确保了两者。

没有这样的限制，组合就行不通。例如，对于您的构造，NFA fora*b*也接受ababab，这是错误的。