# Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars:

Construct a Turing machine that decides whether $$L(G) = L(H)$$, where $$G$$ and $$H$$ are two context free grammars.

This question is taken from Sipser's book on theory of computation.

My current idea is given that $$G$$ and $$H$$ are CFG's, we know that there exists push down automata that accept the languages described by $$G$$ and $$H$$. We can simulate a PDA on a Turing machine and hence, we can convert the problem to the equality of Turing machines, such that $$M_1$$ and $$M_2$$ are TMs and $$L(M_1) = L(M_2)$$ which is known to be undecidable.

My question is, are these steps fine to do (with a bit more formalism)?

## 1 Answer

Let me prove that the problem of determining whether $$x = 0$$ is undecidable.

Let $$A$$ be a Turing machine that accepts only $$x$$, and let $$B$$ be a Turing machine that accepts only $$0$$. Then $$x = 0$$ iff $$L(A) = L(B)$$, so according to your argument, determining whether $$x = 0$$ should be undecidable.

I hope that this example helps you understand why your reasoning doesn't work. Instead, try to to use the fact that CFG universality (given a grammar $$G$$ over $$\Sigma$$, does $$L(G)$$ equal $$\Sigma^*$$?) is undecidable.

• I attempted to use the CFG universality as you suggested. This means i assumed that TM $R$ decides the Equality problem of CFG's and then showed that this would result in a TM $S$ which can then solve the CFG universality problem. TM $S$ behaves on input $G_1$ and $G_2$: 1: Simulate R on ($G_1$, $G_3$) where $G_3 = \Sigma^{*}$ 2: If $R$ accepts, accept; otherwise reject Now, i believe that this would solve the CFG universality problem, which is undecidable, and hence TM $R$ can not exist. Is this correct ? – user507237 Oct 14 '18 at 10:08
• This is the idea, though $\Sigma^*$ is not a grammar. – Yuval Filmus Oct 14 '18 at 14:48