The Gateway to Computer Science Excellence
+3 votes
Please ,can somebody  explain this?

Thanks lot :).
in Theory of Computation by Active (1.2k points) | 647 views

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.

4 Answers

+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.

by Active (4.8k points)
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 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)
0 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

by (149 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,352 answers
105,244 users