Re: On CFL equivalence and graph isomorphism

Pablo <pmoisset@altavista.net>
25 Apr 2000 02:25:01 -0400

          From comp.compilers

Related articles
On CFL equivalence and graph isomorphism johnston.p@worldnet.att.net (Paul Johnston) (2000-04-20)
Re: On CFL equivalence and graph isomorphism lex@cc.gatech.edu (2000-04-25)
Re: On CFL equivalence and graph isomorphism colohan+@cs.cmu.edu (Christopher Brian Colohan) (2000-04-25)
Re: On CFL equivalence and graph isomorphism pmoisset@altavista.net (Pablo) (2000-04-25)
Re: On CFL equivalence and graph isomorphism ger@informatik.uni-bremen.de (George Russell) (2000-04-26)
Re: On CFL equivalence and graph isomorphism bdm@cs.anu.edu.au (2000-04-26)
Re: On CFL equivalence and graph isomorphism dmolnar@fas.harvard.edu (David A Molnar) (2000-04-27)
Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27)
| List of all articles for this month |

From: Pablo <pmoisset@altavista.net>
Newsgroups: comp.theory,comp.compilers
Date: 25 Apr 2000 02:25:01 -0400
Organization: University of Southern California, Los Angeles, CA
Distribution: inet
References: 00-04-140
Keywords: parse, theory

It would be nice to have such an algorithm, but I am afraid your
idea does not work.


Imagine this:


You have two reduced grammars that are almost identical. They
differ in a single production rule.


A-> 0B1 in one case and
A-> 1B0 in the other.


Chances are the grammars will generate different languages (it would
be interesting if someone can find a counterexample or prove it is
impossible, I do not have time to play with it now). My point is: the
grammars can generate different languages and yet can have the same
graph you describe. Isomorphism of your graph connecting nonterminal
is not enough to prove equivalence.


You could think your algorithm then can be used for rejection only: if
graphs are not isomorphic then the grammars are not equivalent.
Again, this does not work: the same language can be represented by an
infinite number of very different grammars. If the number of
nonterminals is different then there will be no graph isomorphism,
even when your grammars are equivalent.


And we CAN test graph isomorphism, we just do not know if we can do it
in polytime or not. The brute force approach will work because the
number of possible isomorphisms (between two given graphs) is finite.


Paul Johnston wrote:


> Regarding 'Properties of Context Free Languages' in Hopcroft, Ullman's
> "Introduction to Automata Theory, Languages, and Computation":
>
> They state but do not qualify "There are, however, certain questions
> about CFL's that no algorithm can answer. These include whether two
> CFG's are equivalent, whether [snip] ...".
>
> On proving the finiteness of a CFL, however, one can (paraphrasing)
> assemble a directed graph with a vertex for each variable
> (nonterminal) and an edge from A to B if there is a production of the
> form A -> BC or A -> CB for any C. The language generated is finite
> iff this graph has no cycles.
>
> According to the strategy above, then, it would seem that given two
> CFG's G and G' one could prove their equivalence by comparing the
> structures of their graphs, which I suppose is the 'classic' Graph
> Isomorphism problem.
>
> Therefore, can we not answer the equivalence of two CFL's because we
> cannot solve the isomorphism of their graphs, or is there another
> reason?
>
> Furthermore, what is the state of solving the Graph Isomorhism
> problem? Is there no hope?


Post a followup to this message

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