# How to prove the emptiness of intersection of two context free languages is undecidable?

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?

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.

• Using this would give me the word as well as the indices of the dominos in reverse order right? – Cilenco May 22 '19 at 9:48
• 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. – John L. May 22 '19 at 21:35