GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
39 views
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 (653 points)   | 39 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 (28.5k 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.

http://gatecse.in/identify-the-class-of-a-given-language/

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


Top Users Sep 2017
  1. Habibkhan

    7184 Points

  2. Warrior

    2664 Points

  3. Arjun

    2582 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,151 questions
33,733 answers
79,970 comments
31,120 users