Exercise 23:

{gCFG({a,b})L(g)={a,b}}{GL(G)={w{0,1}kN:value2(w)=3k}}\{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\}\}
Reduce the universality problem on CFGs over {a,b}\{a,b\} to the problem of whether a CFG generates all words over {0,1}\{0,1\} representing a multiple of 33 in binary notation (in particular, the empty word represents 00, which is multiple of 33), 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.