# Deciding whether the language of a CFG equals some specific regular language

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$?

• 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? – Michael Wehar Feb 17 '17 at 5:38
• 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. ☺ – Michael Wehar Feb 17 '17 at 15:08

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.
• Is there an interesting characterization of the languages $A$ such that $L(G) = A$ is decidable? – Gilles 'SO- stop being evil' Feb 17 '17 at 20:55