automation - Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language

Question

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?

Answer 1

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 of +, length of X becomes greater than one |X| >= 1)

Example of this kind of strings can be following:

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 a 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 states.

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

ITs DFA is as given below.