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