pumping-lemma - 用抽引理证明语言不规则

Question

我试图使用抽水引理证明以下语言不规则

L= { a^ib^j | i^2 > j}

对此有什么建议吗？我完全被困住了。

谢谢。

Answer 1

抽水引理说：如果语言 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.

如果您有任何疑问，请随时询问:)

干杯。

Answer 2

假设您选择了字符串：

a^2b^5

阿布布。这是语言。

现在你的对手可以选择 XYZ。

他们的选择： 1.) X(empty)Y(some a's) 2.) X(some a's)Y(some a's and some b's) 3.) X(some a's)Y(some a's)

根据他们可能的选择，您使用 Y^i 增加 Y，其中 i 是您选择的任意数字。

假设他们选择 1。）

X(-)Y(a)Z(abbbbb)

如果你“抽”Y^i 选择 i = 0。新字符串变为 abbbbb。这不是语言。

对对手的每个可能选择重复此操作，如果您可以以一种产生不在语言 L 中的字符串的方式抽出 Y，那么您已成功证明该语言不是正则的。

Answer 3

对于上述答案，“抽水引理说：如果语言 A 是常规语言 => 有一个数字 p（抽水长度），如果 s 是 L 中的任何字符串，使得 |s| >= p，那么 s 可能是分成三块s=xyz，满足如下条件："

您的意思是“如果语言 L 是常规语言”

此外，三个条件
1. xy^iz 在 L 中，每个 i>=0
2. |y|>=0
3. p>=|xy|

第二个应该只是 |y| > 0 不 >=