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?

What exactly do you want? I suggest you revise your question "Could you give me some ideas?" to something more concise and constructive. — Jeff, Jan 25 '13 at 16:19

score 15 · Accepted Answer · edited Dec 14 '18 at 20:50

15

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.

DFA

edited Dec 14 '18 at 20:50

NoSuchUserException

700
1
9
18

answered Jan 26 '13 at 07:26

Grijesh Chauhan

57,103
20
141
208

To draw it DFA see [this answer](http://stackoverflow.com/questions/14122755/what-will-be-the-dfa-for-the-regular-expression-00101011?answertab=votes#tab-top) bit similar – Grijesh Chauhan Jan 26 '13 at 07:45
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. – henry Jan 26 '13 at 16:46
No `W` is just single symbol either `a` or `b` – Grijesh Chauhan Jan 27 '13 at 04:47
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 :-) – henry Jan 27 '13 at 08:53
@Patrick87 yes, sorry I forgot to add two loop. Thanks Patrick! – Grijesh Chauhan Jan 28 '13 at 18:44

score 2 · Answer 2 · answered Jan 25 '13 at 18:28

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.

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. — henry, Jan 27 '13 at 00:27

score 2 · Answer 3 · answered Feb 02 '13 at 13:38

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

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

3 Answers3

Linked