为什么{a^nb^n | n >= 0}不是正则的？

Question

在我正在学习的计算机科学课程中，有一个不是正则语言的例子：

{a^nb^n | n >= 0}

我能理解这不是一个正则表达式，因为没有有限状态自动机/机器可以验证和接受这个输入，因为它缺少一个记忆组件。(如果我错了，请纠正我) 正则语言的维基百科条目也列出了这个例子，但没有提供证明为什么它不是正则的（数学上）。

有谁能为我解惑并提供证明，或者指引我去一个好的资源？

- Christophe Herreman

Answer 1

你要找的是正则语言的泵引理。

这里有一个与你的问题完全相同的例子：

例子：
让 L = {a^mb^m | m ≥ 1}。
那么 L 不是正则的。
证明：让 n 按照泵引理的方式来选取。
让 w = aⁿbⁿ。
让 w = xyz 按照泵引理的方式来分解。
因此，xy²z ∈ L，然而 xy²z 包含的 a 的数量多于 b 的数量。

- cletus

---

最后一个要求需要更好的解释。如果y中a的数量多于b，或者少于b，那么x2yz单词将包含更多某种字母；如果重复x2yz单词，则会破坏字母顺序，其中b应该在所有a之后出现。 - P Shved

不完整的证明。你还没有定义x、y、z。x只有一个限制，即| xy | <= p，其中p是泵浦长度。你需要将证明分为三种情况，基于(a|ab|b)的y字符串，才能使其完整。xy可能包含的b比a多：x=a，y=b^n，z=b。 - oligofren

证明缺少一些部分，因此是不正确的。另外链接已经失效。 - 6infinity8

Answer 2

由于您无法编写有限状态机来“计算”相同的“a”和“b”符号序列。简而言之，FSM无法“计数”。试想一下这样的FSM：您会给符号“a”多少个状态？给“b”多少个？如果您的输入序列更长呢？

请注意，如果您的n ≤ X，其中X是整数值，则可以准备这样的FSM（通过使用具有大量状态但仍为有限数量的状态）；这种语言将是正则的。

- lorenzog

Answer 3

原因是，当输入字符串中'a'和'b'的数量相等时，您必须仅到达最终状态。为了做到这一点，您必须计算出 'a' 和 'b' 的数量，但由于'n'的值可能会达到无穷大，因此使用有限自动机无法计数到无穷大。

这就是为什么 {a^n b^n | n >= 0} 不是正则的原因。

- Ravi Panchal

Answer 4

假设 L = {aⁿbⁿ | n ≥ 0} 是正则的。那么我们可以使用泵引理。

设 n 是泵引理编号。考虑 w = aⁿbⁿ∈L。泵引理声明，你可以将 w 分成 xyz，使得 xy ≤ n，y ≥ 1 且 ∀ i∈ℕ₀: xyⁱz∈L。

使用前两个规则，我们可以很容易地看出，无论如何将 w 划分为 xyz，y 都将只包含 a，而且至少会包含一个这样的字母。根据第三条规则，我们得出结论，a^n-kbⁿ∈L，其中 k = |y| ≥ 1。但是，n-k ≠ n 违反了 L 的定义，因此 a^n-kbⁿ∉L。这是一个矛盾的结论，所以我们得出结论，假设 L 是正则的是不正确的。

- Niki

Answer 5

有限状态自动机没有数据结构（栈）-与下推自动机的情况不同。它可以给你一些'a'后面跟着一些'b'，但不能给出确切数量的'a'以及后面没有'b'。

- Rohit Pratap

Answer 6

泵引理可用于证明一个语言不是正则的，

例如：

令 L = {a^mb^m | m ≥ 1}

那么 L 不是正则的。

证明：

假设 L 是正则的。

令 n 为泵引理中的数。

令 w = a^nb^n。

令 w = xyz 满足泵引理的条件。

现在 y 只包含 'a'，因为 |xy|<= n 且 i = 2 ( 在 xy^iz 中 )。

因此，xy^2z ∈ L，但是 xy^2z 包含比 b 更多的 a。

这与第一个假设相矛盾，所以它不是正则的。

- Sujai Dev

Answer 7

让我用一个例子来解释：

L = {a^n.b^n | n >= 0};

L 中被接受的最小长度字符串是：

{ε, ab, aabb, ...} => 最小 w = ab;

我没有考虑 n == 0，因为对于 n == 0，y 永远不能是 |y| > 0。

首先让我们取 x = ε，然后 y = a，z = b 或者 y = ab，z = ε，因为 |y| > 0 并且 |xy| <= 2（由于它是一个无限语言，p（这里是 2）可以是字符串长度的最大值reference here）

在泵浦 y = a 后：

在泵引数为y = ab的情况下，有以下字符串：

L' = abab, ababab, abababab;

现在，取x = a，y = b和z = ε，在泵引数为y = b的情况下，有以下字符串：

L' = abb, abbb, abbbb, abbbbb;

再次检查w = aabb：w在L中；

对于x可以是ε，a，aa，aab，那么y可以是a，aa，bb，ab，aab，...aabb，而z可以是ε，b，bb，abb。

在上述所有情况中，无论是对于任何长度的y进行泵送后生成的L'，都不会被L所接受。L'要么具有不相等的a、b，要么顺序不符合定义。因此，L = {a^n.b^n | n >= 0} 不是正则的，因为它未能通过正则语言的Pumping lemma for regular languages测试。

- shubhcodegate