20 Apr 2000 01:33:47 -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) |

[1 later articles] |

From: | "Paul Johnston" <johnston.p@worldnet.att.net> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 20 Apr 2000 01:33:47 -0400 |

Organization: | AT&T Worldnet |

Distribution: | inet |

Keywords: | parse, theory, books |

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?

Thanks for your insight,

Paul

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.