theory - 常规语言的 Pumping Lemma 的详细信息

Question

我有一个关于常规语言的抽引引理的小问题 - 是否足以表明如果属于语言 L 的特定字符串无法抽出，那么该语言是不规则的？例如 - 如果我选择语言 L1 的形式为 a^nb^n (ab, aabb, aaabbb ...) 并且我表明字符串 aabb 不能被抽出并且仍然是 L1 的一部分，那么它是对我立即得出 L1 不规则的结论有效吗？

干杯。

Answer 1

是的，这就是抽水引理的工作原理。它仅对证明语言不规则有用。满足抽水引理只是语言正常的必要条件而非充分条件。

（注意事项：对于上下文无关语言和那里的相应抽引引理也是如此）

Answer 2

是的，这就是它的工作原理，但在显示字符串“无法抽水”时要小心

为此，您必须将 L 中的字符串 w 分解为子字符串 xyz 并显示 xy^1z 的某些版本，因为 int i i>=0 导致字符串不在 L 中，但仍被 DFA M 接受（对于 M 内置接受 L)，得出一个矛盾。

请注意，您不能选择 y 的位置，因此必须考虑它的 3 个可能位置。这是关键，在我看来。

Answer 3

仅仅证明单个有限长度的字符串不会抽水是不够的。对于严格的论点，您还必须证明示例字符串的长度大于语言的抽水长度。通常您假设存在某个泵送长度 p，然后构造一个比 p 长且无法泵送的字符串。

Answer 4

抽水引理说：如果语言 A 是规则的 => 有一个数字 p（抽水长度），如果 s 是 L 中的任何字符串，使得 |s| >= p，则 s 可分为三部分 s=xyz，满足如下条件：

1. xy ⁱ z 在 L 中，对于每个 i>=0
2. |y|>=0
3. p>=|xy|

证明某种语言 L 不是正则的正确方法是假设 L 是正则的并试图达到一个矛盾。

让我们尝试证明 L = {0 ⁿ 1 ⁿ }|n>=0} 是不规则的。相反，我们开始假设 L 是正则的。

你可以把这种演示想象成一个游戏：
挑战者：他选择抽水长度 p。你不能对它做任何假设。
你：现在轮到你了：选择代表语言不规则性的字符串“种类”。
假设字符串的形式为 0 ^p 1 ^p。
这一步的一个好技巧是尝试限制对手的下一步行动。
Challenger：他给你一个字符串 s，格式为 0 ^p 1 ^p。
你：是时候抽了！如果您在上一步中正确选择了字符串的形式，您可以做一些假设。
例如，在我们的例子中，我们知道子串 y 仅由 0 组成（至少有一个 0，因为 |y|>0），因为 |xy|<=p 并且第一个 p 元素是 0。

现在我们证明它存在 i>=0 使得 xy ⁱ z 不在 L 中。例如，对于 i=2，字符串 xyyz 的 0 比 1 多，因此不是 L 的成员。这种情况是矛盾的。=> L 不规则。

永远不要忘记证明为什么抽的弦不能是 L.

可能帮助你已经晚了，但其他人可能需要这种解释......也许^^

干杯。