为什么 L={wxw^R|w, x 属于 {a,b}^+ } 是正则语言 [英] Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language

问题描述

使用泵引理，我们可以很容易地证明语言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.

你能给我一些想法吗?

推荐答案

如果我们用 x 替换字符 c，其中 (x ∈ {a,b}⁺)，比如说，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 是正则语言 :).

Yes, L2 is Regular Language :).

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

_{You can write regular expression for L2 too.}

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

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

• string 应该以任何由 a 和 b 组成的字符串开头，即 W 并以反向字符串 W^R.
• 注意: 因为 W 和 W^R 彼此相反，所以字符串以相同的符号 开始和结束(可以是 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^R.
• notice: because W and W^R 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^R 等于 a(a + b)⁺a 或b(a + b)⁺b

so any string WXW^R 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^R 与 WCW^R 混用，它的 X 和 + 使语言成为常规.认为通过包含 X 即 (a + b)* 我们可以对 W 有有限选择，即 a 和 b(有限是正则)}

_{Don't mix WXW^R with WCW^R, its X with + that makes language regular. Think by including X that is (a + b)* we can have finite choice for W that is a and b (finite is regular).}

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

Language WXW^R 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}^+ } 是正则语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！