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$?
$\begingroup$
$\endgroup$
2
-
$\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 WeharCommented Feb 17, 2017 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 WeharCommented Feb 17, 2017 at 15:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ Is there an interesting characterization of the languages $A$ such that $L(G) = A$ is decidable? $\endgroup$ Commented Feb 17, 2017 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$ Commented Feb 17, 2017 at 21:22