自动化 – 为什么L = {wxw ^ R | w,x属于{a,b} ^}是常规语言

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

但是,如果我们用“x”(x∈{a,b})替换字符c,比如说,L2 = {WxW ^ R | x,W∈{a,b} ^},则L2是常规语言.

你能给我一些想法吗？

If we replace character c with x where (x ∈ {a,b}⁺), say, L2 = {WXW^R| x, W ∈ {a,b}⁺}, then L2 is a regular language.

是的,L2是常规语言:).

您也可以为L2编写正则表达式.

语言L2 = {WXWR | x,W∈{a,b}}表示：

> string应该启动任何由a和b组成的字符串,该字符串为W,以反向字符串WR结尾.
>注意：因为W和WR是相反的,所以字符串以相同的符号开头和结尾(可以是a或b)
>并且包含中间的任何a和b的字符串是X.(因为X grater的长度然后是一个| X |> = 1)

这个字符串之王的例子可以是：

aabababa,如下：

a    ababab    a  
  --   --------   --
   w     X        W^R

或者它也可以是：

babababb,如下：

b    ababab    b
  --   --------   --
   w     X        W^R

在语言定义中查看W的长度不是约束.

所以任何字符串WXWR都可以假设等于a(a b)a或b(a b)b

a    (a + b)+   a
   ---   --------  ---
    W      X       W^R

要么

b    (a + b)+   b
   ---   --------  ---
    W      X       W^R

此语言的正则表达式为：a(a b)a b(a b)b

不要将WXWR与WCWR混合,它的X与语言有规律.通过包含X来思考(a b)*我们可以对W进行有限选择,即a和b(有限是常规的).

语言WXWR可以说是：如果以a结尾,并且以b开头,b结尾为b.所以相应地我们需要两个最终状态.

> Q6如果W是a
> Q5如果W是b

IT DFA如下所示.