0
$\begingroup$

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'$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – phhoang Nov 16 '15 at 22:20
  • $\begingroup$ parsed by the grammar = accepted in the language, at least in my terminology. And yes, PCP can be reduced to this problem. $\endgroup$ – Hendrik Jan Nov 16 '15 at 22:24
  • $\begingroup$ Recall that an intersection of CFL's is not necessarily a CFL. $\endgroup$ – Ran G. Nov 16 '15 at 22:26
  • $\begingroup$ 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. $\endgroup$ – phhoang Nov 16 '15 at 22:26
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Nov 17 '15 at 2:30
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, I got it. Could you reduce to PCP? $\endgroup$ – phhoang Nov 17 '15 at 0:44

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.