我读到每个非确定性有限自动机(NFA)都可以转换为确定性有限自动机(DFA)。可以对克雷尼星号regex做到这一点吗？
上面是a *的NFA。
最佳答案
是。 Kleene星确定性有限自动机具有两个状态。起始状态是最终状态，并且对于a具有过渡到其自身的状态，对于所有其他符号，具有过渡至另一状态的状态。每个符号的另一个状态都有一个过渡到其自身。
因此，它接受空字符串(因为起始状态为final)和a的任意重复。任何非a的内容都会将DFA发送到另一个状态，该状态是非最终状态，并且无法逃脱。
如果将Kleene星号应用到比单个符号更复杂的正则表达式上，它会稍微复杂一些，但是可以始终这样做:只需将正则表达式的NFA插入所显示图像的红色部分，然后应用标准Powerset construction算法，将NFA转换为DFA。我强烈建议您研究此算法；如果您了解它的工作原理，则将看到为什么每个NFA都可以转换为DFA的原因。
关于regex - Kleene Star的确定性有限自动机，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34971320/