|On CFL equivalence and graph isomorphism firstname.lastname@example.org (Paul Johnston) (2000-04-20)|
|Re: On CFL equivalence and graph isomorphism email@example.com (2000-04-25)|
|Re: On CFL equivalence and graph isomorphism firstname.lastname@example.org (Christopher Brian Colohan) (2000-04-25)|
|Re: On CFL equivalence and graph isomorphism email@example.com (Pablo) (2000-04-25)|
|Re: On CFL equivalence and graph isomorphism firstname.lastname@example.org (George Russell) (2000-04-26)|
|Re: On CFL equivalence and graph isomorphism email@example.com (2000-04-26)|
|Re: On CFL equivalence and graph isomorphism firstname.lastname@example.org (David A Molnar) (2000-04-27)|
|[1 later articles]|
|From:||"Paul Johnston" <email@example.com>|
|Date:||20 Apr 2000 01:33:47 -0400|
|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
Therefore, can we not answer the equivalence of two CFL's because we
cannot solve the isomorphism of their graphs, or is there another
Furthermore, what is the state of solving the Graph Isomorhism
problem? Is there no hope?
Thanks for your insight,
Return to the
Search the comp.compilers archives again.