定义r和r的DFA时寻找r*的DFA

Question

我喜欢这个例子，当r和r的DFA被定义时，这个方法可以找到r*的DFA。以及如何思考？我读了一本课本，但我不太明白。谢谢。

Answer 1

r*是一种语言，它包含0,1,2,3,4，...因此，对于r *，显而易见的FA是可以针对r 0,1,2,3,4，...任何一次运行后，都会执行此操作并接受。从任何接受状态到开始状态的lambda/empty转换将实现1次或更多次运行。由此产生的自动机不再是确定性的。您可以使用标准方法来确定它。这种构造不会将空字符串添加到自动机的语言中。如果它在r中已经存在，那么这是不必要的。否则，您需要在自动机中为r*添加一种接受空字符串的方法，例如，使用新的开始状态。

有了一点消除空转换的经验，您还可以更直接地为简单情况构建DFA。