Ambiguity in the Grammar (S \rightarrow ABA,; A \rightarrow aA \mid \epsilon,; B \rightarrow bB \mid \epsilon)

A context-free grammar is called ambiguous if there exists at least one string in its language that admits two distinct parse trees; equivalently, the same string has two different leftmost derivations or two different rightmost derivations.2 Ambiguity matters because a parser may assign multiple syntactic structures to the same input, which makes interpretation non-unique.2

For the grammar

$$S \rightarrow ABA$$ $$A \rightarrow aA \mid \epsilon$$ $$B \rightarrow bB \mid \epsilon$$

the nonterminal $A$ generates any number of $a$'s, including none, so $L(A)=\{a^i \mid i\ge 0\}$, and $B$ generates any number of $b$'s, including none, so $L(B)=\{b^j \mid j\ge 0\}$.2 Therefore, the start symbol generates strings of the form

$$L(S)=\{a^i b^j a^k \mid i,j,k \ge 0\}.$$

This can also be written as $a^\* b^\* a^\*$.2 The key source of ambiguity is that the two occurrences of $A$ in $S \to ABA$ can both generate $a$-strings, so when a derived string contains only $a$'s, or when the middle $B$ vanishes to $\epsilon$, there may be multiple ways to distribute the same $a$'s between the left and right $A$.2

A compact structural view is:

Because both $A_1$ and $A_2$ can independently derive $a^\*$ and $B$ can derive $\epsilon$, the boundary between the left and right blocks of $a$'s is not unique for some strings.2

Footnotes

1. Parse trees, ambiguity, and Chomsky normal form - Defines ambiguity via existence of a string with at least two parse trees. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. CS 373: Theory of Computation - University of Illinois - Explains ambiguity of CFGs in terms of different parse trees and derivations. ↩ ↩² ↩³

3. Context-Free Grammars and Languages - Discusses ambiguity, parse trees, and why multiple parses create non-unique structure. ↩ ↩²

4. Unambiguous Grammar - Includes this exact grammar as an ambiguity exercise and supports the analysis of how the productions generate strings. ↩ ↩²

Why this grammar is ambiguous

Let us choose the string

$$w = a.$$

This string belongs to $L(G)$ because we may let one $A$ generate $a$, let $B \Rightarrow \epsilon$, and let the other $A \Rightarrow \epsilon$. However, there is also another derivation in which the first $A \Rightarrow \epsilon$, $B \Rightarrow \epsilon$, and the second $A$ generates $a$. Since these correspond to different syntactic structures, the grammar is ambiguous.2

More generally, every string $a^n$ with $n\ge 1$ is ambiguous in this grammar. Since $B \Rightarrow \epsilon$, we have

$$S \Rightarrow ABA \Rightarrow a^i \epsilon a^k = a^{i+k},$$

and for any fixed $n$, there are multiple choices of $(i,k)$ such that $i+k=n$. For example, $a^2$ can be split as $a^2\epsilon\epsilon$, $a\epsilon a$, or $\epsilon\epsilon a^2$. At least two such splits yield distinct parse trees, which is sufficient for ambiguity.2

An abstract view of the ambiguity for $a^n$ is:

Thus the grammar does not assign a unique structure to such strings.2

Footnotes

1. Unambiguous Grammar - Includes this exact grammar as an ambiguity exercise and supports the analysis of how the productions generate strings. ↩ ↩²

2. Parse trees, ambiguity, and Chomsky normal form - Defines ambiguity via existence of a string with at least two parse trees. ↩ ↩² ↩³

3. CS 373: Theory of Computation - University of Illinois - Explains ambiguity of CFGs in terms of different parse trees and derivations. ↩ ↩²

4. Context-Free Grammars and Languages - Discusses ambiguity, parse trees, and why multiple parses create non-unique structure. ↩

Two distinct parse trees for the string (a)

Below are two different parse trees for the same string $a$.

Parse Tree 1: the left $A$ produces $a$, while $B$ and the right $A$ produce $\epsilon$.

Parse Tree 2: the left $A$ produces $\epsilon$, $B$ produces $\epsilon$, and the right $A$ produces $a$.

Since these parse trees are structurally different but yield the same terminal string $a$, the grammar is ambiguous by definition.2

Footnotes

1. Parse trees, ambiguity, and Chomsky normal form - Defines ambiguity via existence of a string with at least two parse trees. ↩

2. CS 373: Theory of Computation - University of Illinois - Explains ambiguity of CFGs in terms of different parse trees and derivations. ↩

Formal interpretation of the chart

For a string $a^n$, if $B \Rightarrow \epsilon$, then the left occurrence of $A$ may generate $a^i$ and the right occurrence may generate $a^{n-i}$ for any integer $i$ with $0 \le i \le n$. Hence the number of possible splits is

$$n+1.$$

So for $n=1$, there are $2$ splits; for $n=2$, there are $3$ splits; and in general the grammar offers multiple structural decompositions of the same terminal string. The existence of more than one valid decomposition for even one value of $n\ge 1$ already proves ambiguity.2

This also shows that the ambiguity is not accidental or isolated: it is a systematic effect caused by overlapping generative roles of the two $A$ nonterminals combined with the epsilon production $B \Rightarrow \epsilon$.2

Footnotes

1. Unambiguous Grammar - Includes this exact grammar as an ambiguity exercise and supports the analysis of how the productions generate strings. ↩ ↩²

2. Parse trees, ambiguity, and Chomsky normal form - Defines ambiguity via existence of a string with at least two parse trees. ↩ ↩²

3. CS 373: Theory of Computation - University of Illinois - Explains ambiguity of CFGs in terms of different parse trees and derivations. ↩