pumping-lemma - 确定正则语言和 CFL 的引理问题

Question

{a^pb^p; p 是素数}

{a^pb^p; p为素数，m为定数，m≥p≥0}

我如何证明这是否是常规语言/上下文无关语言（或不是）？

Answer 1

1) L = {a^nb^n; n 是素数} ：

所以可以用反证法来证明。假设 L 是规则的，p 是泵送长度。

测试字符串为w = a^pb^p，w属于L，|w| = 2p >= p

我们细分 w=xyz。有 3 个条件来证明抽水引理：

• 从第三个条件 |xy| < p，所以 xy 只包含 a
• 从第二个条件 |y| > 0，所以 y 的形式为 y = a^k，其中 1 <= k <= p
• 从第一个条件开始，xy^iz 属于 L for i = 0, 1, 2, ... 所以如果你抽空 (i = 0) 你得到：

w = a^(p - k) b^p ，而 w 不属于 L （因为 a 和 b 的数量不同）

所以你证明 L 不是正则的。