2
$\begingroup$

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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – user507237
    Commented Oct 14, 2018 at 10:08
  • $\begingroup$ This is the idea, though $\Sigma^*$ is not a grammar. $\endgroup$
    – Yuval Filmus
    Commented Oct 14, 2018 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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