6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.