Problem Detail: 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 0right}$ there’s infinitely many ways to derive it? Does this make the grammar infinitely ambiguous?
Asked By : Jakub Lédl
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6357 Ask a Question Download Related Notes/Documents
