# 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!

-

## 1 Answer

There is not. In fact, there isn't even an inefficient way!

That is, the problem of determining whether two given CFGs represent the same language is undecidable. In fact, an even stronger statement is true: the problem of determining whether a given CFG accepts all strings on its alphabet is undecidable.

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

-
Is there any algorithm that works for some practical cases at least? It might be undecidable in general but there may be special cases that can be handled that are sufficient for most use cases... kind of like how making an antivirus is undecidable too, yet people do it anyway... –  Mehrdad Dec 11 '13 at 21:09
@Mehrdad: I don't know of one, but this isn't really my field. You could try asking that as a separate question (either here or on cs.SE). –  Micah Dec 13 '13 at 16:31
I see, ok thanks. –  Mehrdad Dec 13 '13 at 20:09