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?


1 Answer 1


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.

  • $\begingroup$ Using this would give me the word as well as the indices of the dominos in reverse order right? $\endgroup$
    – Cilenco
    Commented May 22, 2019 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$
    – John L.
    Commented May 22, 2019 at 21:35
  • $\begingroup$ can we use the same proof to show that the non emptiness of intersection of two cfls is also non decidable? $\endgroup$
    – rsonx
    Commented Aug 4, 2021 at 17:22
  • 1
    $\begingroup$ @rsonx Checking the non-emptiness is the same as checking the emptiness. If the intersection is empty, then it is not non-empty. If it is not empty, then it is non-empty. $\endgroup$
    – John L.
    Commented Aug 5, 2021 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.