# Context-free language and undecidable

I am working on my midterm sample problems and got stuck on this one. Is this language undecidable?

$\qquad L = \{\langle G_1, G_2 \rangle: G_1, G_2 \text{ are CFG and have strings that can be parsed in both grammars }\}$

Is this one the same as $L' = \{\langle G_1, G_2 \rangle: L(G_1) \cap L(G_2) \ne \emptyset\}$? My professor said the above problem can be reduced to Post Correspondence Problem but I found it closer to the decidable of $L'$.

• I am asking if the two are the same or not, because I am confused; if it is the same, $L'$ can be prove without using PCP. But my professor said it can be reduced to PCP. Nov 16, 2015 at 22:20
• parsed by the grammar = accepted in the language, at least in my terminology. And yes, PCP can be reduced to this problem. Nov 16, 2015 at 22:24
• Recall that an intersection of CFL's is not necessarily a CFL. Nov 16, 2015 at 22:26
• My proof is set $G_2$ to $\Sigma^{*}$ and $L(G_1) \cap L(G_2) \ne \emptyset \Leftrightarrow L(G_1) \ne \emptyset$, which is undecidable ($E_{TM}$ in Sipser's book). But I'm stuck with a proof with PCP. Nov 16, 2015 at 22:26
• Actually emptiness of context-free languages is decidable (a single one, not the intersection of two). Emptiness of TM languages, that is indecidable. Back to the drawing board. Nov 17, 2015 at 2:30

Yes, they are the same languages: $L=L'$ (at least the way that I understand the definition of $L$). We say that the grammar $G_1$ can parse a string $x$ iff $x \in L(G_1)$. It follows that $L=L'$. $L$ is defined in a somewhat informal way; good for you for finding a way to provide a more precise formal statement of it.
Indeed, the problem of deciding whether two CFLs have a non-empty intersection is undecidable, so neither $L$ nor $L'$ is decidable.