4
$\begingroup$

From what I've read, an example of infinite ambiguity is usually given in a form of a loop:

$S \rightarrow aA \\ A \rightarrow B \\ B \rightarrow A \\ B \rightarrow b$

But a grammar is called ambiguous if there's more than 1 way to derive the input string ω. What if I then take this well-known ambiguous grammar:

$S \rightarrow SSS \\ S \rightarrow SS \\ S \rightarrow b$

and extend it with $S \rightarrow \epsilon$ so that for any member of $\left\{ b^n \middle| n \geq 0\right\}$ there's infinitely many ways to derive it? Does this make the grammar infinitely ambiguous?

$\endgroup$

migrated from cstheory.stackexchange.com Oct 28 '12 at 12:55

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ A grammar is infinitely ambiguous iff there is a productive and accessible nonterminal $A$ s.t. $A\Rightarrow^+ A$. Nonterminals $A$ and $B$ fulfill this characterization in your first example, and so does $S$ in the second example when you add the rule $S\rightarrow\varepsilon$. I'll leave the proof of the characterization as an exercise (think that a parse tree of infinite size for a finite input sentence must repeat nonterminal spanning the same interval in the input). $\endgroup$ – Sylvain Oct 28 '12 at 11:46
2
$\begingroup$

From a comment by Sylvain:

A grammar is infinitely ambiguous iff there is a productive and accessible nonterminal $A$ s.t. $A \Rightarrow^+ A$. Nonterminals $A$ and $B$ fulfill this characterization in your first example, and so does $S$ in the second example when you add the rule $S \to \varepsilon$. I'll leave the proof of the characterization as an exercise.

Consider that a parse tree of infinite size for a finite input sentence must repeat a nonterminal spanning the same interval in the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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