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

Question

大多数来源，例如http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html，都表明Kleene闭包由4个节点构成。

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

Answer 1

为了当您连接两个NFA的得到正确的结果，你需要确保这两个组件，或者：

1. 没有转换出最终状态的;或

2. 没有转换到开始状态。

正常的汤普森建筑确保两者。

没有这种限制，构图不起作用。例如，对于您的建筑，a*b*的NFA也接受ababab，这是错误的。