COMPLEMENT OF CSL

Question

Answer 1

If no. of a = no, of b = no. of c = .... e

complement = atleast a single pair which is not equal.

a!=b or a!=c or a!=d or a!=e .... d!=e

We can use PDA to form such language, So CFL.

Comments

L is CSL and CSL is closed under complements..then ...??

---

Yes, CSL is closed under complement.

---

Then it should be CSL..??

---

It is a CFL and a CFL is a strict subset of CSL. Thus, by extension a CFL can be a CSL but the converse need not be true.

---

So if in option they would have given CSL along with CFL then what would have been the answer..??

---

then we should select most appropriate option;

look, if L= {a*};

then what will be the answer ? Regular, CFL, CSL, RE

Obviously Regular.

Answer 2

Is it (B) CFL?