The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
L={ W(W^r) , W ∈ (a,b)* }

W^r is reverse of W.

Is it a regular language ?

please Explain.
asked in Theory of Computation by Junior (955 points) | 41 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


answered by Veteran (31.9k 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

Related questions

+3 votes
0 answers
0 votes
1 answer
+2 votes
1 answer

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

29,115 questions
36,924 answers
34,782 users