为什么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重新presents反向串W）

不过，如果我们替换字符 C 与X（X∈{A，B} +）比方说， L2 = {WXW ^ R | X，W∈{A，B} ^ +} ，然后L2 是一个正则语言

你能不能给我一些想法？

解决方案

  

如果我们替换字符c与x，其中（X∈{A，B} ⁺ ），也就是说，L2 = {WXW ^研究 | X，W∈{A，B} ⁺ }，然后L2为一个普通的语言。

是 L2 是有规律的语言:)。

<子>您可以编写定期EX pression L2 了。

语言L2 = {WXW ^研究 | X，W∈{A，B} ⁺ }意思是：

• 字符串应该启动任何字符串包含 A 和 B 是是W 和反向字符串是W 研究。
结束

• 的通知：的，因为W和是W ^研究是彼此串反向启动，并与同一符号结束的（即可以是在或 b ）的


• 和遏制的任意字符串的的 A 和 B 在中间的那个是 X 。 （因为 + X 磨碎再一个的长度| X |＆GT; = 1 ）

本王的字符串的例子可以follwoing：

aabababa，如下所示：

  A ABABAB一
   -  --------  - 
   W¯¯x宽^ R
 

，或者它可以是也：

babababb，如下所示：

  B ABABAB b
   -  --------  - 
   W¯¯x宽^ R
 

请参阅的长度W 语言定义不限制。

所以任何字符串WXW 研究可以假设等于 A（A + B） + A 或 b（A + b） + b

  A（A + B）+ A
   --- -------- ---
    W¯¯x宽^ R
 

或

  B（A + B）+ B
   --- -------- ---
    W¯¯x宽^ R
 

和这个语言普通防爆pression是： A（A + B） + A + b（A + b） + b

<子>不要混用 WXW 研究与 WCW - [R ，其 X 与 + ，使语言规律。通过包括认为 X 是（A + B）* 我们可以有有限的选择为是W 是 A 和 b （有限是有规律）。

语言 WXW 研究可以说：如果启动与 A 与<结束code> A ，如果下手 b 结束与 b 。所以相应地我们需要两个最终状态。

• Q6如果是W 是 A


• Q5如果是W 是 B

的ITs DFA是如下给出。

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)

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.

Could you give me some ideas?

解决方案

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.

Yes, L2 is Regular Language :).

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

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

• 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 + length of X grater then one |X| >= 1)

Example of this king of strings can be follwoing:

aabababa, as follows:

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

or it can be also:

babababb, as follows:

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

See length of W is not constraint in language definition.

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  

or

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

And Regular Expression for this language is: a(a + b)⁺a + b(a + b)⁺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).}

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 state.

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

ITs DFA is as given below.

这篇关于为什么L = {WXW ^ R | W，X属于{A，B} ^ +}是一个正则语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！