On CFL equivalence and graph isomorphism

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

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