Exercise 11:

{g1,g2CFG({a,b})2L(g1)L(g2)=}{G1,G2L(G1)L(G2)}\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)=\emptyset\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\mathcal{L}(G_1)\subseteq\overline{\mathcal{L}(G_2)}\}
Reduce the empty intersection problem on CFGs over {a,b}\{a,b\} to the inclusion problem between the language of a CFG and the complement of the language of another CFG, in order to prove that such problem is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.