Re: On CFL equivalence and graph isomorphism

lex@cc.gatech.edu
25 Apr 2000 02:08:35 -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)
Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27)
| List of all articles for this month |
From: lex@cc.gatech.edu
Newsgroups: comp.theory,comp.compilers
Date: 25 Apr 2000 02:08:35 -0400
Organization: Georgia Institute of Technology, Atlanta GA, USA
Distribution: inet
References: 00-04-140
Keywords: theory, parse

"Paul Johnston" <johnston.p@worldnet.att.net> writes:
> 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?


Two CFG's might be different but accept the same language. Consider:


                S := a | S a.




versus:


                S := X.
                X := a | X a.




versus:


                S := X.
                X := a | S a.


-Lex

Post a followup to this message

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