将 kleene star 应用于 FSM

Question

在我看到的将 Kleene star 应用于现有 FSM 的所有示例中，我看到创建了一个新的接受和起始状态，并且存在从所有接受状态到该状态的 epsilon 转换以及从新状态到原来的开始状态。我的问题是为什么我们需要一个新的状态？我们不能让原始开始状态成为一个接受状态（如果它还没有接受）并通过 epsilon 转换 link 到所有接受状态吗？

谢谢！

吉尔

Answer 1

因为原来的起始状态可能已经发生了自转移。考虑使用 DFA

的语言 L = a*b

A -a-> A
A -b-> B

以B为接受状态。

如果您使状态 A 接受并添加了转换 B -ε-> A，那么现在语言接受单词 a。 a 不是 L* 的成员，因此这个新的 DFA 不是 L*，而是其他东西。

相反，我们添加一个新的开始接受状态 C:

C -ε-> A
A -a-> A
A -b-> B
B -ε-> C

a 不再被这个 εNDFA 接受。这种语言是 L*.

将 kleene star 应用于 FSM

Applying kleene star to a FSM

regex

automata