2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – Knogger
    Commented Apr 24 at 6:06

1 Answer 1

5
$\begingroup$

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).

I leave it to you to fill in the details and justify each of these steps. This is your exercise, so it will be a good practice for you to fill in the blanks and justify each step.

$\endgroup$
1
  • 1
    $\begingroup$ It would be decidable whether $L(G)=\Sigma^*$... But it's undecidable. Therefore, $L(G')=\Sigma^+$ must be undecidable. Thanks $\endgroup$ Commented Apr 24 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.