The Context-Free Grammar Equivalence Problem
Two grammars G1 and G2 are defined
to be equivalent if they generate the same language.
The grammar equivalence problem is the problem of deciding whether
two context-free grammars are equivalent. This problem is
undecidable .
Suppose that, in a homework problem or a test, I ask you to find a
context-free grammar that generates a given language, or is equivalent
to a given context-free grammar. Grading this homework then becomes
an impossible problem!
You could give me a correct answer to the question which is so complex
that I could not decide whether it is correct. In fact, theoretically,
you could give me a correct answer which is impossible
to prove correct. (Of course, it would be impossible for you to do this
deliberately, because you, yourself, would be unable to prove it correct.)
So, what is the poor grader to do? My answer is this. If there is a simple
and correct answer, and if you give a complicated but correct answer, and
I cannot see that it is correct within a reasonable amount of time,
I will mark it wrong. The alternative is to run the risk of sitting there
grading that problem until the
Day of Doom.
Back to
Course Page