regex - Kleene Star 的确定性有限自动机

Question

我读到每个非确定性有限自动机（NFA）都可以转换为确定性有限自动机（DFA）。这可以为kleene star regex做吗，比如a *？

以上是 a* 的 NFA。

Answer 1

是的。Kleene 星确定性有限自动机有两种状态。起始状态是最终状态，并且对于 具有到自身a的转换，对于所有其他符号具有到其他状态的转换。对于每个符号，另一个状态都有到自身的转换。

因此，它接受空字符串（因为起始状态是最终状态）和任意次数的a. 任何不是a的都会将 DFA 发送到另一个状态，这是非最终的，并且无法逃脱。

如果您将 Kleene 星应用于比单个符号更复杂的正则表达式，它会稍微复杂一些，但始终可以做到：只需将正则表达式的 NFA 插入您显示的图像的红色部分，然后应用将 NFA 转换为 DFA 的标准Powerset 构造算法。我强烈推荐学习这个算法；如果您了解它的工作原理，您就会明白为什么每个 NFA 都可以转换为 DFA。

Answer 2

它只是一个单一的起始状态，也是接受状态。它有一个接受'a'的自循环。