Re: On CFL equivalence and graph isomorphism

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?

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