Is the set {p | Lp is context free} decidable, semidecidable, or not semidecidable?

229 Views Asked by At

I have done some research and I know that it can be proven that every CFL is decidable (for example: https://pdfs.semanticscholar.org/f719/739f07c24c3790b63f3274037522b0b831c8.pdf). This means that we can build a TM/algorithm which takes a CFL and a word w and tells whether this word w belongs to CFL, and this algorithm halts.

But I don't know if this fact can be used to prove that the set {p | Lp is context free} is decidable. As far as I'm concerned, the problem of saying whether a set is decidable or not is that we can build an algorithm that halts that can tell in finite time whether an element belongs to this set or not.

Edit: Let me clarify. p is a program. Lp is L(p), the language of the words accepted by p.