snippetMinor
How to prove the emptiness of intersection of two context free languages is undecidable?
Viewed 0 times
emptinesstheundecidablehowfreelanguagesprovetwointersectioncontext
Problem
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?
Do you maybe have a book or paper I should investigate?
Solution
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.
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.
Context
StackExchange Computer Science Q#109510, answer score: 8
Revisions (0)
No revisions yet.