我正在学习自动机。你能帮我理解带 Kleene 闭包的自动机是如何工作的吗？假设我有字母 a、b、c，我需要找到以 Kleene 星号结尾的文本 - 例如 ab*bac - 它如何工作？
最佳答案
问题似乎更多地是关于自动机如何处理 Kleene 闭包，而不是 Kleene 闭包意味着什么。
有了一个简单的正则表达式，例如 abc，设计一个自动机来识别它就非常简单了。每个状态基本上都会告诉您到目前为止您在表达式中的位置。状态 0 意味着它还没有看到任何东西。状态 1 表示它看到了 a。状态 2 表示已看到 ab。等等
Kleene 闭包的困难在于像 ab*bc 这样的模式会引入歧义。一旦自动机看到了 a，然后又遇到了 b，它不知道 b 是否是 的一部分>b* 或它后面的文字 b，直到它读取更多符号后才会知道——也许更多。
简单的答案是自动机只是有一个状态，字面意思是它还不知道采取了哪条路径。
在简单的情况下，你可以直接构建这个自动机。在一般情况下，您通常会构建一种称为非确定性有限自动机的东西。您可以模拟 NDFA，或者——如果性能至关重要——您可以应用一种算法将 NDFA 转换为确定性算法。该算法实质上会为您生成所有不明确的状态。
关于algorithm - 带有 kleene star 的自动机，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10986605/