Kleene Star的确定性有限自动机

Question

我读到每个非确定性有限自动机（NFA）都可以转换成确定性有限自动机（DFA）。这可以做为克莱恩星正则表达式，说一个*？

以上是a *的NFA。

Answer 1

是的。 Kleene星形确定型有限自动机有两种状态。起始状态是最终的，并且对于a有一个转换到它自己，并且对于所有其他符号转换到另一个状态。另一个州对每个符号都有一个过渡。

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

如果将Kleene星形应用于比单个符号更复杂的正则表达式，它会变得稍微复杂一些，但它总是可以完成的：只需将正则表达式的NFA插入到显示的图像的红色部分，并应用标准Powerset construction算法将NFA转换为DFA。我强烈建议学习这种算法;如果你理解为什么它的作品，你会看到为什么每个NFA可以转换成DFA。

Answer 2

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