This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.

##
Exercise
_{‹}25:

$\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{0,1\}^* \mid \exists k\in\mathbb{N}: \mathtt{value}_2(w)=3\cdot k+2\}\}$

Reduce the universality problem on CFGs over $\{a,b\}$ to the problem of
whether a CFG generates all words over $\{0,1\}$ representing a multiple of $3$
plus $2$ in binary notation (in particular, the empty word represents $0$,
which is multiple of $3$), in order to prove that such problem is not
semi-decidable (not recursively enumerable).

Authors: Carles Creus, Guillem Godoy
/

Documentation: