## Exercise ‹5›:

$\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3,G_4\rangle\in\mathtt{CFG}(\{a,b\})^4\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_3)\cap\mathcal{L}(G_4)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_4)=\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)=\emptyset\}$
Reduce the non-empty intersection problem on CFGs over $\{a,b\}$ to the set of tuples of four CFGs $G_1,G_2,G_3,G_4$ whose alphabet is $\{a,b\}$ such that $G_1$ and $G_2$ generate at least one common word, $G_3$ and $G_4$ generate at least one common word, but $G_1$ and $G_4$ do not generate a common word, and $G_2$ and $G_3$ do not generate a common word, in order to prove that such set is undecidable (not recursive).
Authors: Guillem Godoy / Documentation:
 input g1,g2 { // Write your reduction here... // output ... , ... , ... , ... ; } To be able to submit you need to either log in, register, or become a guest.