5
$\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$
1
  • 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, 2012 at 11:46

1 Answer 1

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 and acknowledge you have read our privacy policy.

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