Regular

Question

L={xwwr |x,w∈(a+b)+}     this is not regular

proof ?

Comments

http://gatecse.in/wiki/Identify_the_class_of_the_language

Answer 1

L={XWW^r| X,W∊(a+b)⁺}

Here WW^r is NCFL(because we can push all the term of W in a stack and W^r pop those terms.So it is CFL and also here middle term is not known . So it is NCFL)

here X is regular i.e.(a+b)⁺

Now reguler .CFL= CFL [Only phi . CFL=phi i.e. regular, but here phi is not possible , as X= (a+b)⁺ ]

So, it cannot be regular

Comments

ParimalAndhalkar

ya of course this is cfl .I am asking?

Can,t you say reg.cfl=reg? In any case?

---

Yes it is possible in many cases.

---

Thanks  sir .

So we cant say it is always Cfl .it is reg also.