25 Sep 2004 13:07:25 -0400

Related articles |
---|

Proof of inherent ambiguity? dave_140390@hotmail.com (2004-09-24) |

Re: Proof of inherent ambiguity? nsanders@wso.williams.edu (Nathan Sanders) (2004-09-25) |

Re: Proof of inherent ambiguity? dido@imperium.ph (Rafael 'Dido' Sevilla) (2004-09-25) |

Re: Proof of inherent ambiguity? torbenm@diku.dk (2004-09-25) |

Re: Proof of inherent ambiguity? b.scott@csuohio.edu (Brian M. Scott) (2004-09-25) |

Re: Proof of inherent ambiguity? rdecker@hamilton.edu (Rick Decker) (2004-09-25) |

Re: Proof of inherent ambiguity? Michael.J.Fromberger@Dartmouth.EDU (Michael J. Fromberger) (2004-09-25) |

Re: Proof of inherent ambiguity? hmessinger@comcast.net (Harlan Messinger) (2004-10-02) |

From: | "Brian M. Scott" <b.scott@csuohio.edu> |

Newsgroups: | comp.compilers,comp.theory,sci.lang |

Date: | 25 Sep 2004 13:07:25 -0400 |

Organization: | Compilers Central |

References: | 04-09-137 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2004 13:07:25 EDT |

On 24 Sep 2004 00:26:52 -0400, Dave Ohlsson

<dave_140390@hotmail.com> wrote in sci.lang:

[...]

*> Could anyone give an example of an inherently ambiguous context-free*

*> language AND the proof that that language is inherently ambiguous?*

The language

{a^n b^n c^m d^m : n, m in N} U {a^m b^n c^n d^m : n, m in N}.

context-free and inherently ambiguous. The proof is long and

tedious and depends on the fact that there will always be two

different parse trees for some of the strings in the intersection

of the two pieces of the language. I believe that it can be

found in Hopcroft and Ullman, Introduction to Automata Theory.

Brian

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.