Re: Grammar equivalence (Stavros Macrakis)
1 May 1996 23:21:57 -0400

          From comp.compilers

Related articles
Grammar equivalence (Gabor DEAK JAHN) (1996-04-29)
Re: Grammar equivalence (Christian Rinderknecht) (1996-04-30)
Re: Grammar equivalence (1996-05-01)
Re: Grammar equivalence (1996-05-06)
| List of all articles for this month |

From: (Stavros Macrakis)
Newsgroups: comp.compilers
Date: 1 May 1996 23:21:57 -0400
Organization: OSF Research Institute
References: 96-04-158 96-04-163
Keywords: parse, theory

Christian Rinderknecht <> 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


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.