Cheap and Secure Web Hosting Provider : See Now

[Solved]: Hardness of ambiguity/non-ambiguity for context-free grammars

, , No Comments
Problem Detail: 

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ 1 \ |\ ... $$ because the string 1+2*3 can be parsed as (1+2)*3 and 1+(2*3). For context free grammars (CFGs) ambiguity is not decidable [1, 2]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and non-ambiguity cannot even be recursively enumerable, for otherwise ambiguity of a given CFG $G$ could be decided by running the enumeration of ambiguity and non-ambiguity together and seeing which one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?

  1. D. G. Cantor, On The Ambiguity Problem of Backus Systems.

  2. R. W. Floyd, On ambiguity in phrase structure languages.

Asked By : Martin Berger

Answered By : Yuval Filmus

Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback