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

Question

使用泵引理,我们可以很容易地证明,语言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 是一个普通的语言.

你能给我一些想法吗？

Answer 1

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

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

_{你也可以编写正则表达式L2.}

语言L2 = {WXW ^R | x,W∈{a,b} ⁺ }表示:

• 串应该开始的任何字符串包括a和b是W和具有反向串W底^{- [R} .
• 注意:因为W和W ^R是相反的,所以字符串以相同的符号开头和结尾(可以是a或者b)
• 并包含任何字符串的a,并b在中间的那个就是X.(因为+,长度X变得大于1 |X| >= 1)

这种字符串的示例如下:

aabababa,如下:

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

或者它也可以是:

babababb,如下:

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

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

所以任何字符串WXW ^R都可以假设等于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

_{不要将WXW^R与WCW^R混合,它X与+语言有规律.通过包括认为X这是(a + b)*我们可以有有限的选择了W这是a和b(有限是有规律的).}

语言WXW^R可以说是:如果以a结尾a开头,如果从b结尾开始b.所以相应地我们需要两个最终状态.

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

IT DFA如下所示.