使用pumping引理证明下列语言不是正则语言L= {anbm |n= 2m}

Question

利用pumping引理证明下列语言不是正则语言L= {an bm |n= 2m}

Answer 1

选择一个字符串a^2p b^p。pumping引理说我们可以写成w= uvx，使得|uv| <= p，|v| <0，对于所有自然数n，u(v^n)x也是语言中的字符串。因为| uv | <= p，w的子串uv完全由符号a的实例组成。通过为n选择一个不是1的值来向上或向下提升，可以保证结果字符串中a的数量将发生变化，而b的数量保持不变。因为只有当n= 1时，a的数量才是b的两倍，这是一个矛盾。因此，语言不能是常规的。