25 Sep 2004 11:29:45 -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: | Nathan Sanders <nsanders@wso.williams.edu> |

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

Date: | 25 Sep 2004 11:29:45 -0400 |

Organization: | Compilers Central |

References: | 04-09-137 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2004 11:29:45 EDT |

dave_140390@hotmail.com (Dave Ohlsson) wrote:

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

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

I think the following might be what you are looking for:

L = {a^i b^j c^k | i=j or j=k}

Looking at strings like aabbcc, aaabbbccc, it seems that every grammar

must have at least two different parse trees, one for matching a's and

b's with arbitrary trailing c's, and one for matching b's and c's with

arbitrary preceding a's.

I'm not sure about a formal proof, though. I'm a bit rusty!

Nathan

--

Nathan Sanders

Linguistics Program nsanders@wso.williams.edu

Williams College http://wso.williams.edu/~nsanders

Williamstown, MA 01267

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.