# Context sensitive language is context free

Problem of determining whether a context sensitive language is context free is undecidable.

How to prove it

Let $$C$$ be a family of languages effectively closed under union and concatenation with regular sets, and for which equality to $$\Sigma^*$$ is undecidable (for sufficiently large $$\Sigma$$). Let $$P$$ be a proper subset of $$C$$, which contains all regular languages, and is closed under single letter quotient. Then membership of $$P$$ is undecidable for $$C$$.
So, we have to check whether the context-sensitive and context-free languages meet the criteria of Greibach for $$C$$ and $$P$$.
• Basically this uses contradiction. If your question would be decidable, then one could decide that $L(G) = \Sigma^*$ for a context-free grammar $G$, which contradicts the fact that we can't. It is a complete puzzle to me how NP or pumping lemma are related to this problem? – Hendrik Jan Dec 9 '18 at 15:24