|grammars firstname.lastname@example.org (2003-08-04)|
|Re: grammars Ralf.Laemmel@cwi.nl (Ralf Laemmel) (2003-08-10)|
|Re: grammars email@example.com (Carl Cerecke) (2003-08-10)|
|Re: grammars firstname.lastname@example.org (Rob Arthan) (2003-08-10)|
|From:||Carl Cerecke <email@example.com>|
|Date:||10 Aug 2003 10:55:01 -0400|
|Posted-Date:||10 Aug 2003 10:55:01 EDT|
> Can all ambiguous grammars be changed into unambiguous grammars?
> [Well, sure, you can delete stuff until it's not ambiguous any more.
> But I presume the question you're asking is whether there's always an
> unambiguous grammar that recognizes the same language as an ambigous
> one. -John]
Assuming Context Free Grammars (CFGs), there are languages which can
be described by an (ambiguous) CFG for which no unambiguous CFG
exists. Such languages are called "inherently ambiguous".
An example is the language:
a^n b^n c^n d^n , n > 0 (i.e. n a's followed by n b's followed by ..)
Google with "inherently ambiguous" reveals much more.
Return to the
Search the comp.compilers archives again.