Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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