3 votes
3 votes
L={WX$W^{R}$ / W,X$\epsilon (a+b)^{*}$.}

L={XW$W^{R}$ / W,X$\epsilon (a+b)^{*}$.}

l={W$W^{R}$X /W,X $\epsilon (a+b)^{*}$.}

which of the above are REGULAR LANGUAGES.?

------------------------------------------------------------------------------------------------------------------------

I think all are regular

I)w=$\epsilon$ then w^r=$\epsilon$ and x=$(a+b)^{*}$  // it accept complete language so it is regular.

same as for remaining problems also.am i ryt???
in Theory of Computation
468 views

4 Comments

only 1st is regular
nd w is not predefined as epsilon it is only for 1st.
think abt wwx is it cfl ?
same condition on w,x  as above
1
1
@saurabh

in the 2nd and 3rd options

take x=$(a+b)^{*}$ and w=$\epsilon ,w^{r}=\epsilon$ it accept complete language.
2
2
^ i think u r right
1
1

Good thought.

For a minimum string of the form wwr would be 00 or 11 (atleast of len 2)  if $\sum ^{*}\epsilon \left ( 0 + 1 \right )$ * by your claim a substring has to be the form $\epsilon \epsilon$ right?  but  $\epsilon \epsilon$ = $\epsilon$ isn't? Operating on epsilon would mean anything not neccessarily  wwr

0
0

1 Answer

4 votes
4 votes
Best answer

                 all are regular 

  • reg exp: a(a+b)*a + b(a+b)*b
  • reg exp:(a+b)*
  • reg exp:(a+b)*
selected by

3 Comments

^ what abt if w,x is (a+b)+

0
0

^If w , x = (a+b)+,

1.  wxwr = regular. L = a ( a+b)+ a + b ( a + b)+ b

2. xwwr = CFL.

3. wwrx = CFL.

??

2
2
yes,@vijaycs
2
2