在上下文无关语言上抽取引理
Pumping Lemma On Context Free Language
对于语言
{a^2^n | n >= 0}
我知道首先选择一些 k，然后 z = uvwxy 这样 vx != epsilon 和 #(vwx) <= k，但我想不出任何 i 来证明这种语言不是上下文无关。
这里有个提示：如果你考虑任何大于 k 的 2 的幂（比如 2k），那么 2k + k 不是 2 的幂，因为
2k + k < 2k + 2k = 2k+1
看看是否可以指导您选择正确的字符串并找到您选择的 i。
希望对您有所帮助！
对于语言 {a^2^n | n >= 0}
我知道首先选择一些 k，然后 z = uvwxy 这样 vx != epsilon 和 #(vwx) <= k，但我想不出任何 i 来证明这种语言不是上下文无关。
这里有个提示：如果你考虑任何大于 k 的 2 的幂（比如 2k），那么 2k + k 不是 2 的幂，因为
2k + k < 2k + 2k = 2k+1
看看是否可以指导您选择正确的字符串并找到您选择的 i。
希望对您有所帮助！