Exercise 5:

{g1,g2CFG({a,b})2L(g1)L(g2)}{G1,G2,G3,G4CFG({a,b})4L(G1)L(G2)    L(G3)L(G4)    L(G1)L(G4)=    L(G2)L(G3)=}\{\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}\{a,b\} to the set of tuples of four CFGs G1,G2,G3,G4G_1,G_2,G_3,G_4 whose alphabet is {a,b}\{a,b\} such that G1G_1 and G2G_2 generate at least one common word, G3G_3 and G4G_4 generate at least one common word, but G1G_1 and G4G_4 do not generate a common word, and G2G_2 and G3G_3 do not generate a common word, in order to prove that such set is undecidable (not recursive).
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.