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

问题描述

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

Using pumping lemma, we can easily prove that the language L1 = {WcW^R|W ∈ {a,b}*} is not a regular language. (the alphabet is {a,b,c}; W^R represents the reverse string W)

然而，如果我们将字符 c 替换为 "x"(x ∈ {a,b}+)，例如 L2 = {WxW^R|x,W∈{a,b}^+}，那么L2是正则语言.

However, If we replace character c with "x"(x ∈ {a,b}+), say, L2 = {WxW^R| x, W ∈ {a,b}^+}, then L2 is a regular language.

你能给我一些想法吗?

推荐答案

是的，L2 是正则语言 :).

Yes, L2 is Regular Language :).

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

Language L2 = {WXW| x, W ∈ {a,b}} means:

• string 应该以任何由 a 和 b 组成的字符串开头，即 W 并以反向字符串 W 彼此相反，所以字符串以相同的符号 开始和结束(可以是 a 或 b)
• 并且在中间包含a和b的任意字符串，即X.(因为+，X的长度变得大于1|X| >= 1)

• string should start any string consist of a and b that is W and end with reverse string W.
• notice: because W and W are reverse of each other so string start and end with same symbol (that can be either a or b)
• And contain any string of a and b in middle that is X. (because of +, length of X becomes greater than one |X| >= 1)

此类字符串的示例如下:

Example of this kind of strings can be following:

aabababa，如下:

aabababa, as follows:

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

也可以是:

巴巴巴，如下:

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

请参阅W 的长度不是语言定义中的约束.

See length of W is not a constraint in language definition.

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

so any string WXW can be assume equals to a(a + b)a or 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

And Regular Expression for this language is: a(a + b)a + b(a + b)b

语言WXW 可以说:如果以a 开始，以a 结束，如果以b 以 b 结尾.所以相应地我们需要两个最终状态.

Language WXW can be say: if start with a ends with a and if start with b end with b. so correspondingly we need two final states.

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

• Q6 if W is a
• Q5 if W is b

IT 的 DFA 如下所示.

ITs DFA is as given below.

这篇关于为什么 L={wxw^R|w, x 属于 {a,b}^+ } 是正则语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！