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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– CilencoCommented 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$– rsonxCommented 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