This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\overline{\mathcal{L}(G_1)}\subseteq\mathcal{L}(G_2)\}$
Reduce the universality problem on CFGs over $\{a,b\}$ to the inclusion problem
between the complement of the language of a CFG and 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: