Exercise 21:

{gCFG({a,b})L(g)={a,b}}{GL(G)={w{a,b}:wa=wb}}\{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=|w|_b\}\}
Reduce the universality problem on CFGs over {a,b}\{a,b\} to the problem of whether a CFG generates the words over {a,b}\{a,b\} with as many occurrences of aa as occurrences of bb, 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.