patternMinor
What precisely is infinite ambiguity in a grammar?
Viewed 0 times
infinitewhatambiguitygrammarprecisely
Problem
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?
$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?
Solution
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.
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.
Context
StackExchange Computer Science Q#6357, answer score: 2
Revisions (0)
No revisions yet.