computer-science - 为什么是 {a^nb^n | n >= 0} 不规则？

Question

在我正在学习的 CS 课程中，有一个不规则语言的示例：

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

我可以理解这是不规则的，因为由于缺少内存组件，因此无法编写有限状态自动机/机器来验证和接受此输入。（如果我错了请纠正我）

正则语言上的维基百科条目也列出了这个例子，但没有提供（数学）证明它为什么不是正则的。

任何人都可以启发我并为此提供证据，或者给我一个很好的资源吗？

Answer 1

您正在寻找的是Pumping lemma for regular languages。

这是您的确切问题的示例：

示例：
令 L = {a ^m b ^m | 米≥1}。
那么 L 不是正则的。
证明：令 n 与 Pumping Lemma 中的一样。
让 w = a ⁿ b ⁿ。
令 w = xyz 与 Pumping Lemma 中的一样。
因此，xy ² z ∈ L，然而，xy ² z 包含的 a 比 b 多。

Answer 2

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

请注意，如果您有 n <= X 且 X 为整数值，您可以准备这样的 FSM（通过让一个具有很多状态，但仍然是有限数）；这种语言将是常规的。

Answer 3

原因是，只有在没有的情况下，您才必须达到最终状态。'a' 和没有。'b' 在输入字符串中相等。要做到这一点，你必须同时计算两者，没有。'a' 以及没有。'b' 但因为 'n' 的值可以达到无穷大，所以使用有限自动机无法计数到无穷大。

这就是为什么 {a^nb^n | n >= 0} 不规则。

Answer 4

有限状态自动机没有数据结构（堆栈） - 内存，就像下推自动机一样。是的，它可以给你一些'a'，然后是一些'b'，但不是'a'的确切数量，然后是'b'。

Answer 5

假设L = {a ⁿ b ⁿ | n ≥ 0}是正则的。然后我们可以使用抽水引理。

令n为抽水引理数。考虑w = a ⁿ b ⁿ ∈L。抽水引理指出，您可以将w划分为xyz，使得xy ≤ n，y ≥ 1和∀ i∈ℕ ₀ : xy ⁱ z∈L。

使用前两个规则，我们可以很容易地看到，无论我们如何将w划分为xyz，y总是只包含一个s 并且它将包含至少一个这样的字母。根据规则 3，我们得出结论a ^n-k b ⁿ ∈L其中k = |y| ≥1。但是nk ≠ n违反了L的定义，因此a ^n-k b ⁿ ∉L。这是一个矛盾我们得出结论， L是正则的假设是错误的。

Answer 6

让我在这里用一个例子来解释：

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

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

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

我没拿n == 0，既然换了n == 0，y就永远不可能了|y| > 0。

让我们先取x = ε, 然后y = aand z = bor y = aband z = ε，因为|y| > 0and |xy| <= 2（因为它是一种无限的语言， （这里 2）可以和这里的字符串引用p长度一样大）

抽水后y = a：

L' = aab, aaab, aaaab, aaaaab;

抽水后y = ab：

L' = abab, ababab, abababab;

现在，取x = a，然后y = b和z = ε；抽水后y = b：

L' = abb, abbb, abbbb, abbbbb;

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

for xcan be ε, a, aa, aab, then ycan bea, aa, bb, ab, aab, ... aabb 和zcan be ε, b, bb, abb;

在上述所有情况下L'，抽水后产生的任何长度均y不予受理L。L'要么 a、b 不相等，要么顺序不符合定义。因此，L = {a^n.b^n | n >= 0};不是常规的，因为它无法为常规语言抽引引理。