On CFL equivalence and graph isomorphism

"Paul Johnston" <johnston.p@worldnet.att.net>
20 Apr 2000 01:33:47 -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)
[1 later articles]
| List of all articles for this month |

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.