相关疑难解决方法(0)

使用泵引理,我们可以很容易地证明,语言L1 = {WcW^R|W ? {a,b}*}是不是正规的语言.(字母是{a,b,c}; W ^ R代表反向字符串W)

然而,如果我们替换字符c用"x"(x ? {a,b}+),比如说L2 = {WxW^R| x, W ? {a,b}^+},则L2 是一个普通的语言.

你能给我一些想法吗？