regular-language - 使用 Pumping Lemma 证明语言不规则的提示

Question

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

L = {a ⁱ b ^j | i = 2j 对于某些 j ≥ 0}

我决定选择 s = a ^2p b ^p，这样 |s| ≥ p，我可以将它分成三部分 xyz，其中对于每个 i ≥ 0，xy ⁱ z ∈ L。

继续证明的任何提示？

谢谢！

Answer 1

选择 s = a ^2p b ^p是对的！

正如 Grijesh Chauhan 所说，我们必须以所有可能的方式打破 L 中的字符串。

因此，您可以将 s 拆分为：

• x=a ^k
• y= ^al
• z=a ^2p-kl b ^p

其中 |xy|≥ 0 且 |y|>0。

取 i=2，你有 xy ² z：

• s = a ^k a ^l a ^l a ^2p-kl b ^p

那是：

• s = a ^2p+l b ^p

因为 l 至少包含一个 'a'（因为 |y|>0）。你可以说 L 不是正则