Kleene Star 的确定性有限自动机
Deterministic Finite Automaton of Kleene Star
我读到每个非确定性有限自动机 (NFA) 都可以转换为确定性有限自动机 (DFA)。这可以为 kleene star 正则表达式完成吗，比如 a*?
以上是 a* 的 NFA。
是的。 Kleene 星确定性有限自动机有两个状态。起始状态是最终状态，对于 a 有到自身的转换，对于所有其他符号有到其他状态的转换。对于每个符号，另一个状态都有一个到自身的转换。
因此，它接受空字符串（因为起始状态是最终状态）和任意数量的 a 重复。任何不是 a 的东西都会将 DFA 发送到另一个状态，即 non-final，并且无法逃脱。
如果将 Kleene star 应用于比单个符号更复杂的正则表达式，它会稍微复杂一些，但总能做到：只需将正则表达式的 NFA 插入图像的红色部分即可显示，并应用标准 Powerset construction 算法将 NFA 转换为 DFA。我强烈建议学习这个算法；如果您了解它的工作原理，您将看到 为什么 每个 NFA 都可以转换为 DFA。
它只是一个单一的起始状态，也是接受状态。它有一个接受 'a'.
的自循环
我读到每个非确定性有限自动机 (NFA) 都可以转换为确定性有限自动机 (DFA)。这可以为 kleene star 正则表达式完成吗，比如 a*?
以上是 a* 的 NFA。
是的。 Kleene 星确定性有限自动机有两个状态。起始状态是最终状态，对于 a 有到自身的转换，对于所有其他符号有到其他状态的转换。对于每个符号，另一个状态都有一个到自身的转换。
因此，它接受空字符串（因为起始状态是最终状态）和任意数量的 a 重复。任何不是 a 的东西都会将 DFA 发送到另一个状态，即 non-final，并且无法逃脱。
如果将 Kleene star 应用于比单个符号更复杂的正则表达式，它会稍微复杂一些，但总能做到：只需将正则表达式的 NFA 插入图像的红色部分即可显示，并应用标准 Powerset construction 算法将 NFA 转换为 DFA。我强烈建议学习这个算法；如果您了解它的工作原理，您将看到 为什么 每个 NFA 都可以转换为 DFA。
它只是一个单一的起始状态，也是接受状态。它有一个接受 'a'.
的自循环