25 Apr 2000 02:25:01 -0400

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) |

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.