context-free-language - 使用抽引引理证明一种语言不是上下文无关的？

Question

我试图证明语言 L = {a^n! | n>=0} 不是使用泵引理的上下文无关的。但我被困在如何划分 uvxyz 本身。由于它只有一个符号，我觉得它非常棘手。

Answer 1

看看从 L 中抽取给定单词 w 得到的语言 P。在 |vy| 的距离内有 w 本身和无限多个更长的单词。从下一个开始，因为每次抽水都会增加 |vy| 符号。

另一方面，两个阶乘之间的差距一直在变大。显然，例如 (|vy|+2)！- (|vy|+1)！> |维|。但这意味着 P 中有一些单词在 a^(|vy|+1) 之间！和 a^(|vy|+2)!。由于这个词不在 L 中，因此违反了泵送条件。