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'$.
Context-free language and undecidable
computability;context free;formal grammars
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.