# An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate the same things, and only the same things, by trial and error).

Thanks!

-

The proof of this can be found in chapter 5 of Sipser's Introduction to the Theory of Computation. The basic idea is that, for any Turing machine $M$, we can obtain a context-free grammar which accepts all strings that do not encode a proof that $M$ halts (under some specific encoding that's more complicated than I really want to get into here). So determining whether this grammar accepts all strings is equivalent to solving the halting problem for $M$.