Exercise 13:

{gCFG({a,b})L(g)={a,b}}{G1,G2L(G1)L(G2)}\{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\overline{\mathcal{L}(G_2)}\}
Reduce the universality problem on CFGs over {a,b}\{a,b\} to the inclusion problem between the complement of 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.