我知道如何将 Kleene 星应用于语言，但我不确定如何将其应用于 DFA 或 NFA。我很确定它需要是初始状态为最终状态的 epsilon NFA，最终状态可能需要 epsilon 转换到该初始状态？
有什么算法可以实现这一点吗？这个接受以 0 开头并以 1 结尾的单词的 DFA 在应用 Kleene 星号后会如何？ 
最佳答案
在我见过的至少一个关于正则表达式和有限自动机等价性的证明中，给出了一种构造来展示如何将具有与正则表达式 s 对应的语言的 NFA 转换为具有某种语言的 NFA对应于表达式 s* 的值。我认为构造是这样的:
- 新的初始状态 q0' 也接受
- 从 q0' 到前初始状态 q0 的 lambda/epsilon/empty 转换
- lambda/epsilon/empty 从每个接受状态(q0' 除外)转换回 q0'
这允许:
- 要接受的空字符串，即使它之前不是
- 接受原始 NFA 语言中的任何字符串连接
关于algorithm - 如何在自动机上应用 Kleene 星？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/72140110/