The Gateway to Computer Science Excellence
+1 vote
L={ W(W^r) , W ∈ (a,b)* }

W^r is reverse of W.

Is it a regular language ?

please Explain.
in Theory of Computation by Junior (779 points) | 58 views
No. You can check it using pumping lemma.
It is CFL. A nondeterministic pda can accept it.

1 Answer

+2 votes
Best answer

wwR is CFL.

  • NPDA can simulate it.
  • It cannot be simulated by DPDA. 
  • It is not regular.

NB : wxwR is regular

by Boss (33k points)
selected by

wxwR is regular only if w,x both belong to (a,b)*, right? If x belongs to some other element group then it will not be regular.


@warlock lord Check here more such questions.

Yes that is what I meant to ask if w belongs to (a,b)* but x belongs to (c,d)*.. will it still be regular?

I'm just pointing out that "wxwR" is not simply regular. It has to belong to the same symbol group
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,405 answers
105,468 users