Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

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  
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). –  Sylvain Oct 28 '12 at 11:46

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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