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\{G\mid\mathcal{L}(G)=\{w\in\{a,b\}^* : |w|_a\neq|w|_b\}\}$
Reduce the universality problem on CFGs over $\{a,b\}$ to the problem of
whether a CFG generates the words over $\{a,b\}$ where the number of
occurrences of $a$ is different from the number of occurrences of $b$, in order
to prove that such problem is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy
/
Documentation: