1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.