2
$\begingroup$

I was wandering if $L = \{\langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = A \}$ is decidable where A is a some regular language. Is $L' = \{ \langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = \overline A \}$ decidable ? I feel like $L'$ should be decidable, but can't see how. Or does it depends on $A$?

$\endgroup$
  • $\begingroup$ Neat question! Are you asking if L(G) = A for a particular A that you fixed. Or, are you asking is L(G) is a regular language? $\endgroup$ – Michael Wehar Feb 17 '17 at 5:38
  • $\begingroup$ It seems that the question was clarified to be about a particular fixed A. Thank you. I think that the other question is interesting as well though. ☺ $\endgroup$ – Michael Wehar Feb 17 '17 at 15:08
4
$\begingroup$

It depends on your choice of $A$. For example, the problem $\{\langle G \rangle \mid L(G) = \Sigma^* \}$ is undecidable, while $\{\langle G \rangle \mid L(G) = \phi \}$ is decidable.

Also, the two languages that you have given (the one with $A$ and the other with $\overline{A}$) are equivalent since regular languages are closed under complementation.

$\endgroup$
  • 1
    $\begingroup$ Is there an interesting characterization of the languages $A$ such that $L(G) = A$ is decidable? $\endgroup$ – Gilles Feb 17 '17 at 20:55
  • 1
    $\begingroup$ Unfortunately, I am not aware of any such characterization. But it's an interesting question and I suggest that you post it as another question. $\endgroup$ – skankhunt42 Feb 17 '17 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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