theory - 在上下文无关语言上抽取引理

Question

对于语言 {a^2^n | n >= 0}

我知道首先选择了一些 k，然后 z = uvwxy 使得 vx != epsilon 和 #(vwx) <= k，但我想不出任何 i 可以证明这种语言不是上下文无关的。

Answer 1

这里有一个提示：如果您考虑任何大于 k 的 2 的幂（例如 2 ^k），那么 2 ^k + k 不是 2 的幂，因为

2 ^k + k < 2 ^k + 2 ^k = 2 ^k+1

看看这是否可以指导您选择正确的字符串并找到您选择的 i。

希望这可以帮助！