regular-language - 使用抽水引理表明以下语言不是正则语言 L = {anbm | n = 2m}

Question

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

标签： regular-languageautomatafinite-automatapumping-lemma

Answer 1

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