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?

Damaris

What exactly do you want? I suggest you revise your question "Could you give me some ideas?" to something more concise and constructive. – Abductor

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.

Syconium

To draw it DFA see this answer bit similar – Syconium

Does it mean we can not just pick one of x strings? As the example you mention above, If we just select x = “ababab” and w = a^n, then we get wxw^R = (a^n)ababab(a^n). However, if we use pumping lemma, it seems that this example fails. That's the part I am confused. When should we choose an appropriate couterexample with pumping lemma. For the example wxw^R, we can not fix x, say x = specific strings, if we fix it, we fail to pass pumping lemma. – Damaris

No W is just single symbol either a or b – Syconium

I know why I am confused. We still can apply pumping lemma in to the second language, say, xy^(2)z = a^(n+|y|) baaba^(n) (we randomly select x=baab). We note that xy^(2)z also = a^(n) a^(|y|)baab a^(n). This is still in the language L, no contradiction. Previous, I mistake this as a contradiction. It is nothing to do with whether we fix x or not. No matter what strings we select from x, we still can get strings that belong to language L. Thanks @Grijesh :-) – Damaris

@Patrick87 yes, sorry I forgot to add two loop. Thanks Patrick! – Syconium

Answer 2

Any string in the language with |W| > 1 can be interpreted as a string in the language where |W| = 1. Thus, a string is in the language if it begins and ends with the same symbol. There are two symbols: a and b. So that language is equivalent to the language a(a+b)(a+b)*a + b(a+b)(a+b)*b. To prove this, you should formalize the argument that "if y is in WxW, then y is in a(a+b)(a+b)*a + b(a+b)(a+b)*b; and if y is in a(a+b)(a+b)*a + b(a+b)(a+b)*b, then y is in WxW".

It doesn't work in the other case since c is a fixed symbol, and can't include all but the characters on the ends. As soon as you bound the length of "x" in your example, the language becomes non-regular.

Fenn

My original wrong method is like --> We a specific "x", say x = abab, then when we applying pumping lemma, it turns out a contradiction. BUT this is a wrong method. We cannot specify any string of "x" and use pumping lemma to prove it. – Damaris

Answer 3

The question says W ∈ {a,b}^+ , so a^n(a+b)a^n should be in the language L2. Now there is no such DFA that will accept the string a^n(a+b)a^n because, after accepting n number of a and (a+b)^+, there is no way for the dfa to remember exactly how many a it accepted in the begining, so L2 should not be regular.........But every where i search for this answer it says it is regular.....this bugs me

Laurielaurier