25 Apr 2000 02:08:35 -0400

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) |

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.