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/

The Gateway to Computer Science Excellence

+3 votes

+1

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/

+2 votes

w,x belongs to(a,b)*

To omit w , we can put epsilon in place of w and w^{R}.

we can say x eats w and w^{R}and we can ignore w and w^{R} by expanding x. and that makes wxw^{R }regular.

But in www^{R, }we cannot do as there is a dependency between w and second w as well as w and w^{R}

So it is not regular.

+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

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,352 answers

198,473 comments

105,244 users