Kleene Star 确定性有限自动机

Question

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

以上是 a* 的 NFA。

Answer 1

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

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

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