# Proof that the set of all universal CFGs is co-RE complete

Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$.

Enumerate the r.e. sets by $W_n$.

Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$.

On page 4 of these lecture notes, to show $\text{EMPTY}\leq\Sigma^*\text{CFL}$ the author constructs a function $g\colon\mathbb{N}\to\{0,1\}^*$ such that

$$n\in\text{EMPTY}\iff L(g(n))\in\Sigma_n^*.$$

I think we actually want $n\in\text{EMPTY}\iff L(g(n))\in\Sigma_{g(n)}^*$. Is this correct?

In the proof we construct grammar $g(n)$ such that it has same alphabet as the Turing machine + symbols for states + separator "#", which is defined to be:
$\Sigma_n = \{0, 1, \triangleright, B, \#, q_0, q_1 . . , q_n \}$
So essentially $\Sigma_n = \Sigma_{g(n)}$. $\Sigma_n$ is a superset of $\{0, 1, \triangleright, B\}$.