5
$\begingroup$

Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.

Do you maybe have a book or paper I should investigate?

$\endgroup$
8
$\begingroup$

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.

The following is a proof taken from this note by Rob van Glabbeek.


Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.

Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem. Given a set $d_1,\cdots,d_n$ of dominos where, for $i=1,\cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars

$$W\to w_1Wd_1\mid w_2Wd_2\mid\cdots\mid w_nWd_n\mid w_1d_1\mid w_2d_2\mid\cdots\mid w_nd_n$$ and $$X\to x_1Xd_1\mid x_2Xd_2\mid\cdots\mid x_nXd_n\mid x_1d_1\mid x_2d_2\mid\cdots\mid x_nd_n.$$

Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.

$\endgroup$
  • $\begingroup$ Using this would give me the word as well as the indices of the dominos in reverse order right? $\endgroup$ – Cilenco May 22 at 9:48
  • $\begingroup$ Let $s$ be generated by $W$, i.e., $s=w_{i_1}w_{i_2}\cdots w_{i_k}d_{i_k}\cdots d_{i_2}d_{i_1}$. If it is also generated by $X$, then $s=x_{i_1}x_{i_2}\cdots x_{i_k}d_{i_k}\cdots d_{i_2}d_{i_1}$. Cancelling $d_{i_k}\cdots d_{i_2}d_{i_1}$, we get $w_{i_1}w_{i_2}\cdots w_{i_k}=x_{i_1}x_{i_2}\cdots x_{i_k}$. Treating $d_i$ as the domino $\dfrac{w_i}{x_i}$, we get $d_{i_1}d_{i_2}\cdots d_{i_k}=\dfrac{w_{i_1}}{x_{i_1}}\dfrac{w_{i_2}}{x_{i_2}}\cdots\dfrac{w_{i_n}}{x_{i_n}}$, where the top and bottom are the same string. $\endgroup$ – Apass.Jack May 22 at 21:35

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.