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
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).