8,863 views
3 votes
3 votes
Please ,can somebody  explain this?

Thanks lot :).

4 Answers

2 votes
2 votes

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.

1 votes
1 votes
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
1 votes
1 votes
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.
1 votes
1 votes

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

Related questions

1 votes
1 votes
1 answer
1
3 votes
3 votes
3 answers
2
Durgesh Singh asked Jul 25, 2017
5,472 views
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong
1 votes
1 votes
3 answers
3