Now, we show that the emptiness problem for LBAs, $$ E_{LBA} = \{\langle M \rangle \mid \text{$M$ is an LBA and $L(M) = \emptyset$} \}$$ is undecidable.
Theorem. $E_{LBA}$ is undecidable.
Proof. We define the notion of an LBA $B$ which recognizes the language of accepting computation histories of $M$ on $w$. Then $L(B)$ is empty if there are no accepting computation histories of $M$ on $w$, which means that $M$ doesn't accept $w$.
A computation history $C = C_1, \dots, C_\ell$ is given as a string $\langle C \rangle = \# C_1 \# \cdots \# C_\ell \#$. Then $B$, on some input string $x$, checks whether the string conforms to this $\#$-delimited format and the following conditions:
Now, suppose that the TM $R$ decides $E_{LBA}$. Then we can construct the following TM to decide $A_{TM}$.
Then if $R$ accepts $\langle B \rangle$, $L(B) = \emptyset$, which implies that $M$ has no accepting computation history on $w$. If $R$ rejects $\langle B \rangle$, the language of $B$ is nonempty, which means $M$ accepts $w$.
Thus, we have a TM that decides $A_{TM}$, but $A_{TM}$ is undecidable, so $E_{LBA}$ must be undecidable. $$\tag*{$\Box$}$$
Now, we return to the problem of showing that $EQ_{CFG}$ is undecidable. First, we show that a related problem, universality for CFGs, is undecidable: $$ALL_{CFG} = \{\langle G \rangle \mid \text{$G$ is a CFG and $L(G) = \Sigma^*$} \}$$
Theorem. $ALL_{CFG}$ is undecidable.
Proof. Again, we will assume that $ALL_{CFG}$ is decidable and show that doing so will allow us to decide $A_{TM}$. We will construct a CFG $G$ that accepts all strings if and only if $M$ does not accept $w$. In particular, if $M$ accepts $w$, $G$ will not generate the accepting computation history for $M$ on $w$.
What does an invalid accepting computation history look like? Recall that a computation history is a string in the format $\# C_1 \# \cdot \# C_\ell \#$. Then we check for one of the following:
The idea is that if $M$ doesn't accept $w$, then there is no accepting computation history for $w$ and every string is an invalid accepting computation history.
We proceed to construct a PDA $D$ to check this for us. Recall that a pushdown automaton is, informally, an NFA with a stack. Also remember that we can transform a CFG to a PDA and vice-versa.
Then $D$ operates as follows: on an input word $x$, we nondeterministically check each of the three conditions. If any of the branches is satified, we can accept. Checking $C_1$ and $C_\ell$ is straightforward, so we will go through checking $C_i$ in more detail.
In this branch, we nondeterministically check each $C_i$, which begins at a $\#$. We then read $C_i$ push each symbol onto the stack until we reach the next configuration denoted by $\#$. We then pop $C_i$ from the stack to compare with $C_{i+1}$.
This works conceptually, but there is a slight technical problem: pushing $C_i$ onto the stack means that it is popped in reverse order. This is easy to fix: simply write every other configuration in reverse order.
Thus, $D$ recognizes all of the strings that are not valid accepting computation histories of $M$ on $w$. We can convert $D$ into a grammar $G'$ and use a TM that decides $ALL_{CFG}$ to decide if $G'$ is universal or not. As detailed at the beginning of the proof, $G'$ is universal if and only $M$ does not accept $w$. Thus, $ALL_{CFG}$ is undecidable. $$\tag*{$\Box$}$$
Finally, we can show that $EQ_{CFG}$ is undecidable.
Theorem. $EQ_{CFG}$ is undecidable.
Proof. If we have a TM $R$ that decides $EQ_{CFG}$, then we can decide $ALL_{CFG}$ with the following machine:
But ALL_{CFG} is undecdiable, so $EQ_{CFG}$ must also be undecidable. $$\tag*{$\Box$}$$