Exercise 6:

{g1,g2CFG({a,b})2L(g1)L(g2)}{G1,G2L(G1)L(G2)2}\{\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\rangle\mid|\mathcal{L}(G_1)\cap\mathcal{L}(G_2)|\geq 2\}
Reduce the non-empty intersection problem on CFGs over {a,b}\{a,b\} to the set of pairs of CFGs whose intersection has at least two elements, 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.