647 views

Thanks lot :).
| 647 views
+1

If w $\in$ { a + b }* then both are regular.
If w $\in$ {a + b}^+ then what you said in question is correct.

See this: Much more such examples are there.
http://gatecse.in/identify-the-class-of-a-given-language/

w,x belongs to(a,b)*

To omit w , we can put epsilon in place of w and wR.

we can say x eats w and wRand  we can ignore w and wR by expanding x. and that makes wxwregular.
But in wwwR, we cannot do as there is a dependency between w and second w as well as w and wR
So it is not regular.

by Active (4.8k points)
0
can you please explain more,how 'x' does not depends on 'w' and 'w^R'?
+1 vote
we can expand x and x eats up both w and w^R  but in case of www^R it is not possible we are unable to give any regular expression.so it is not regular language
by (365 points)
+1 vote
WxW^R is regular because of the fact that you can expand x to both sides as given x belongs to (a,b)*... now by expanding i mean to say;;

example- w=abb x=(a,b)*

wxwR= abbxbba as you know x is not defined so that we can expand x to both ends, in other words, x is treated as bbbb such that language looks like starting and ending with a. and DFA can accept it.

coming to wwwR it is not regular even it is not CFL because of ...let w=ab then wwwR= ab ab ba now it is impossible for DFA and PDA to store and compare even with a stack.
by Active (3.6k points)

WXW^r is regular for W belonging to (a+b)*.

But ww itself is not regular and even not cfl since stack only gives top but we need the bottom of stack to compare ww. Hence a turing machine with linear space can accept it. Hence WWW^r is not REGULAR no CFL but a CSL

by (149 points)

+1 vote