ME Test Series

Question

I know compleiment of CSL is CSL so can anyone explain how to solve these type of problems effectively by saving time.

Comments

In this question I think L1 is a non deterministic CFL and every CFL is a CSL so L1 is CSL is true.

"Complement of a language is a language  of same type" is undecidable  problem for CFL so we can't say anything about it. In this case they have proved by giving a counter example that L2 has a CFG.

---

L1={aa,bb abab, baba,aabb,bbaa,........}

L2={ Ɛ ,a,b,ab,ba,aaab,aabb......}

One way can be to draw a pda and check for L2.If we can draw then it is a CFL and in this case non deterministic Pda is possible. I am also confused now

---

given ans is right

https://gateoverflow.in/43562/toc?show=43595

Answer 1

there exists only few given languages that are csl and the language given above which is CFL is also some few exceptional cases that occurs . apart from that its hard to device a grammar CSL and its barely asked anywhere. further the above case is unique , remember it for next time as its very very rare that someone will ask you to a question like above with languge not  same as above

edit : please not that complement of CSL is not CSL , since if it was then every CFL is CSL and complement of CFL is not CFL its REL