# Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

If $$G$$ is a CFG, is it decidable whether $$L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I thought about $$\overline{VALCOMPS_{M,x}}$$ and that doesn't seem to work as $$\overline{VALCOMPS_{M,x}}$$ is $$\Delta^*$$ if $$M$$ doesn't halt on $$x$$ and $$\Delta^*\setminus\{\text{Some finite set}\}$$ otherwise. So it remains to check whether $$VALCOMPS_{M,x}=\{\epsilon\}$$ which I am not sure if it is decidable. I don't feel it's decidable.

More generally, if $$G$$ is a CFG, and $$L$$ is some language (fixed beforehand), is it decidable whether $$L(G)=L$$? I know the claim is false for $$L=\Sigma^*$$, and true if $$L$$ is finite, but is it true for some infinite set that is not the universal language? If so, what's a characterization for such sets?

Help would be appreciated

• You've mentioned, that you know that $L(G) = \Sigma^*$ is undecidable. Assume (BWOC) that you can decide $L(G) = \Sigma^+$, can you also decide $L(G) = \Sigma^*$? (Hint: Look at $G$s CNF) Commented Apr 24 at 6:06

It is decidable whether $$\epsilon \in L(G)$$. Given a context-free grammar $$G$$, you can construct a new context-free grammar $$G'$$ such that $$L(G')=L(G) \cap \Sigma^+$$. If $$L(G')=\Sigma^+$$ and $$\epsilon \in L(G)$$, then $$L(G)=\Sigma^*$$; if not, then $$L(G) \ne \Sigma^*$$. Therefore, if it were decidable whether $$L(G')=\Sigma^+$$, it would be decidable whether _________ (you fill in the blank). But it is known that it is undecidable whether $$L(G)=\Sigma^*$$. Therefore, ______ (you fill in the blank).
• It would be decidable whether $L(G)=\Sigma^*$... But it's undecidable. Therefore, $L(G')=\Sigma^+$ must be undecidable. Thanks Commented Apr 24 at 7:01