TOC - Self Doubt

Question

Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$

And if $CFL$ can you write the equivalent $CFG$ for this ?

Answer 1

My approach:

consider it as ${ww}$, the language will belongs to CSL

and if we complement it, $\overline{ww}$ so it must be CSL due to CSL is closed under complement.

Comments

The question is if it is CFL or not – it is surely CSL.

Answer 2

 

complement(ww) This language is context free it was proved in the following paper:

Tomaszewski, Zach. "A Context-Free Grammar for a Repeated String." Journal of Information and Computer Science, 2012 (PDF).

 

 

Comments

Are you sure it was first proved in this paper (2012)?

---

I'm not sure if it was proven first in this paper 😅...just know that was

---

Because I remember studying this in college and it was before 2012 :)

---

😅😅😅 I was so sure I got this right when I was solving pyqs. Cuz you instantly think... cfl not closed under complementation. So it is CSL. well..it definitely is but it is ALSO cfl. Then I started googling why and how and found this and other same results