Is L CFL or not?

Question

L ={ww | w ∈{a, b}∗}
Is compliment of L,  CFL? Support with reason

Comments

@atul_21 L is CSL but its complement is CFL (TimeStamp = 1:08:00)
https://www.youtube.com/watch?v=w5LHEu49VlU&list=PL7HjUNIdk93ThXvz2Oa_g30Jt3Owwm4HZ&index=8&t=4080s&fbclid=IwAR3jMkZSCu4fJa2HpnwNGoq0xqdzkpml-ZZZab6zC2kDZryqas5xrPLnG0A

---

Nice video.

Answer 1

It is CFL.

Here if the string is of Odd length then it will never be of the form $ww$, 

And if it is of even length then to prevent it from being of the form $ww$,we can follow the strategy described below.

 

Answer 2

L is Csl .

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

compliment of csl is also csl.

https://gatecse.in/closure-property-of-language-families/

Comments

Its obvious that it is CSL ,I am asking for CFL . Can it be CFL?

---

The complement of L is CSL only. Because even for the complement, you need to check WW which cannot be done with the help of a stack.

---

The set of strings in L are {aa,bb,aaaa,abab,baba,bbbb,aaaaaa,…}. We cannot accept these strings using an NFA. Now, even a PDA is not possible as once we store w on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize L. Now, L can be accepted by a TM in linear space and hence L is CSL.