使用抽水引理来表明以下语言不是常规语言L = {anbm | n = 2m}

Question

使用抽水引理表明以下语言不是常规语言L = {an bm | n = 2m}

Answer 1

选择字符串a ^ 2p b ^ p。抽水引理说我们可以写成w = uvx使得| uv | <= p，| v | <0，并且对于所有自然数n，u（v ^ n）x也是该语言中的字符串。因为| uv | <= p，w的子字符串uv完全由符号a的实例组成。通过为n选择一个非1的值来进行上乘或下乘保证了结果字符串中a的数目将改变，而b的数目保持不变。因为仅当n = 1时a的数量是b的数量的两倍，所以这是一个矛盾。因此，语言不能是常规语言。