|Grammar equivalence firstname.lastname@example.org (Gabor DEAK JAHN) (1996-04-29)|
|Re: Grammar equivalence Christian.Rinderknecht@inria.fr (Christian Rinderknecht) (1996-04-30)|
|Re: Grammar equivalence email@example.com (1996-05-01)|
|Re: Grammar equivalence firstname.lastname@example.org (1996-05-06)|
|From:||email@example.com (Stavros Macrakis)|
|Date:||1 May 1996 23:21:57 -0400|
|Organization:||OSF Research Institute|
Christian Rinderknecht <Christian.Rinderknecht@inria.fr> writes:
...I wondered if it was possible to show that, given two grammars
(the first and the last), they describe the same language. The
answer it NO. It is an undecidable problem....
"Undecidable" means that the problem cannot be solved _in general_.
However, it does _not_ mean that particular instances cannot be
solved. How difficult the original problem is depends on what sorts
of "simplifications" and "changes" are involved. I admit that even
the "simple" cases are likely to be combinatorially difficult, but
sometimes that is still tractable. For that matter, it may be good
enough for the original problem to produce some sort of "diff" of the
two grammars, reducing a large number of rules to compare to a small
Return to the
Search the comp.compilers archives again.