Regular language

Question

How to check whether the language is regular or not ? { wxw | w,x belongs to (a+b)raise to +}

Comments

it is regular language.you can check by giving the regular expression for it.it is same as a$(a+b)^{+}$a +b($(a+b)^{+}$b,a($(a+b)^{+}$b,b$(a+b)^{+}$a..

---

this is not regular.

wxw. Let W=01   X= 100

wxw= 01 100 01.Since there is no mention about the lentgh of X,we try to match elements as many as we can to make it regular.In worst case , even if you go till last but one, LHS has 0 and RHS has 1. W  cant take two different values 0,1.

If it had been WXW^R  IT is regular.

 

Answer 1

It is regular.

Lets see the strings in L
= { a, b, aa, ab, ba, bb, aaa, ..... } (When w is ϵ, wxw generates all these strings and hence we don't need to consider any other case for w)
= Σ* - {ϵ}
As we have no restriction on the length of x, we can leave 1st and last symbol as it is and consider the rest part as x.

eg : w=bab x=bb

wxw = babbbbab; we may assume x = abbbba so we can read it as : bxb which is finite.

 

Comments

@ arvin ,you are correct it's not a regular language.for ex take string=000111,0011,10,1100,111000 etc.it does not satisfy the condition of WXW.

---

I think it should not   be regular as we have flexibility  in managing  x and  But keeping that first and last symbol would not be same when we take w =ab it would satisfy the regular expression

---

yes it aint :)

Answer 2

$a(a+b)^+  a +b(a+b)^+b+ ab(a+b)^+ab+ ba(a+b)^+ba $