algorithm - 带有克莱恩星的自动机

Question

我正在学习自动机。你能帮我了解一下带 Kleene 闭包的自动机是如何工作的吗？假设我有字母 a、b、c，我需要找到以 Kleene 星号结尾的文本——比如 ab*bac——它将如何工作？

Answer 1

Kleene 星号('*') 表示您可以根据需要多次出现该字符（0 次或更多次）。 a*将匹配任意数量的 a。

(ab)*将匹配任意数量的字符串“ab”

如果您尝试匹配表达式中的实际星号，那么您编写它的方式完全取决于您正在使用的正则表达式的语法。对于一般情况，反斜杠\用作转义字符：

\*将匹配一个星号。

要在最后识别模式，请使用连接：

(a U b)*c*将匹配任何结尾包含 0 个或多个 'c'，前面有任意数量的 a's 或 b's 的字符串。

对于以 Kleene 星号结尾的匹配文本，同样，您可以有 0 次或多次出现该字符串：

ab(c)*- 可能的匹配项：ab、abc、abcc、abccc 等。

a(bc)*- 可能的匹配项：a、abc、abcbc、abcbcbc 等。

Answer 2

这个问题似乎更多地是关于自动机如何处理 Kleene 闭包，而不是 Kleene 闭包的含义。

使用简单的正则表达式，例如 ，abc设计一个自动机来识别它是非常简单的。每个状态基本上都会告诉您到目前为止您在表达式中的位置。状态 0 意味着它还没有看到任何东西。状态 1 表示已看到a。状态 2 表示已看到ab。等等。

Kleene 闭包的困难在于，像这样的模式会ab*bc引入歧义。一旦自动机看到了a并且然后面对 a b，它就不知道那b是它的一部分b*还是它后面的文字b，并且在它读取更多符号之前它不会知道 - 可能更多。

简单的答案是自动机只是有一个状态，字面意思是它还不知道走哪条路。

在简单的情况下，您可以直接构建此自动机。在一般情况下，您通常会构建一种称为非确定性有限自动机的东西。您可以模拟 NDFA，或者 - 如果性能很关键 - 您可以应用一种将 NDFA 转换为确定性算法的算法。该算法本质上为您生成了所有模棱两可的状态。

Answer 3

您在英语中的表达 ab*bac 会是这样的：

a 后跟 0 个或多个 b 后跟 bac

strings that would evaluate as a match to the regular expression if used for search

abac
abbbbbbbbbbac
abbac

strings that would not match

abaca //added extra literal
bac //missing leading a

如上一个答案所述，实际搜索 * 需要一个特定于实现的转义字符，并且需要了解您选择的语言/库。