This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\{\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\in\mathtt{CFG}(\{a,b\})^2\mid|\mathcal{L}(G_1)\cap\mathcal{L}(G_2)|\geq 2\}$
Reduce the non-empty intersection problem on CFGs over $\{a,b\}$ to the set of
pairs of CFGs with alphabet $\{a,b\}$ whose intersection has at least two
elements, in order to prove that such set is undecidable (not recursive).
Authors: Guillem Godoy
/
Documentation: