Ambiguity in Grammar and a Proof of Ambiguity for a Given CFG

Ambiguity in grammar (especially in context-free grammars) means that one string in the language can be generated in more than one distinct way—typically formalized as producing two different parse trees (or equivalently, two different leftmost/rightmost derivations).
For a context-free grammar (CFG), a string $w$ is ambiguous with respect to the grammar if there exist at least two different parse trees whose yields (leaves, read left-to-right) form $w$.

Key terms:

• Ambiguous grammar
• Parse tree
• Leftmost derivation
• Rightmost derivation

To show a grammar is ambiguous, a standard method is:

1. Find a string $w$ derivable by the grammar.
2. Exhibit two distinct parse trees for $w$ (or two distinct leftmost derivations).
3. Conclude the grammar is ambiguous because ambiguity requires only one witness string.

Footnotes

1. Wikipedia — Ambiguity in context-free grammars (general definition). https://en.wikipedia.org/wiki/Context-free_grammar#Ambiguity - Explains ambiguity as multiple parse trees/derivations for the same string. ↩

2. Wikipedia — Parse tree and derivations concepts. https://en.wikipedia.org/wiki/Parse_tree - Background on parse trees (tree structure reflecting derivations). ↩ ↩²

We are given the CFG:

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

What strings does it generate?

From $A \rightarrow aA \mid \varepsilon$, each $A$ generates a sequence of zero or more $a$’s; similarly, $B$ generates zero or more $b$’s.
Therefore, any derivation from $S$ has the form:

$$S \Rightarrow A\,B\,A \Rightarrow a^{i}\, b^{j}\, a^{k}$$

for some $i,j,k \ge 0$.
So the language is:

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

(We will not need the full characterization to prove ambiguity—only one witness string.)

Key idea
Here, ambiguity will come from the fact that both occurrences of $A$ generate $a$-strings, so the same overall $a$-block can be partitioned between the left $A$ and the right $A$ in more than one way.

Footnotes

1. Wikipedia — Context-free grammar productions and language generation (rules like $A \to aA \mid \varepsilon$ yield $a^*$). https://en.wikipedia.org/wiki/Regular_grammar - Covers how recursive productions with $\\varepsilon$ generate repetition languages; applicable to the behavior of $A$ and $B$ here. ↩

A correct ambiguity proof: the grammar is ambiguous

We will show that there exists a string $w$ such that two distinct parse trees exist.

However, for this particular grammar, observe the structure of $S \rightarrow ABA$:

• The middle portion must be produced entirely by $B$ (only $b$’s).
• The left and right portions around $B$ are produced by two separate $A$’s (only $a$’s).

That implies any derived string has the form:

$$a^{i}\, b^{j}\, a^{k}.$$

Now consider $w = aba$, i.e. $i=1, j=1, k=1$.
In order to obtain exactly one $a$ before the $b$, the left $A$ must generate exactly one $a$, i.e. $A \Rightarrow a\varepsilon$.
Similarly, to obtain exactly one $a$ after the $b$, the right $A$ must also generate exactly one $a$, i.e. $A \Rightarrow a\varepsilon$.
The middle $b$ forces $B \Rightarrow b\varepsilon$.

So for $w=aba$, the parse tree structure is essentially forced:

• Left $A$ must be $a\varepsilon$
• Middle $B$ must be $b\varepsilon$
• Right $A$ must be $a\varepsilon$

That suggests no ambiguity for that string.

The subtlety

To prove ambiguity, we need a string for which there are two different ways to assign productions to nonterminals that still yield the same terminal string. Here, because:

• $B$ generates only $b$’s, and the grammar has exactly one $B$ in the skeleton $A\,B\,A$,
• and both $A$’s generate only $a$’s with no way for $a$’s to “move” across the $B$,

the partition point between the $a$-region and the $b$-region is determined by the position of the $b$’s in the final string. Likewise, the partition of the prefix and suffix $a$’s is tied to the fact that both $A$ occurrences correspond to the two sides of the single $B$.

Result: this CFG is unambiguous for all strings it generates because the decomposition $a^{i} b^{j} a^{k}$ matches a unique choice of $(i,j,k)$, and for each $i$ (resp. $k$) there is only one derivation shape for $A \Rightarrow a^{i}$ (it must apply the $aA$ rule exactly $i$ times then $\varepsilon$ once).

[Warning]{type="warning"}
If you were expecting a straightforward “two parse trees for the same string” example, note that this grammar’s structure can make such a witness difficult or impossible—so ambiguity must be checked carefully with explicit derivations. (A common mistake is to assume “multiple $A$’s implies ambiguity,” but here the terminals are segregated: $A$ produces only $a$ and $B$ produces only $b$.)

Formal justification via uniqueness of derivation counts

For $A$:

• Producing $a^{i}$ requires applying $A \rightarrow aA$ exactly $i$ times, then $A \rightarrow \varepsilon$.
• That yields a unique parse tree shape for that $i$ (a chain of length $i$ ending in $\varepsilon$).

For $B$ similarly:

• Producing $b^{j}$ requires applying $B \rightarrow bB$ exactly $j$ times, then $B \rightarrow \varepsilon$.

Thus, for any specific string $a^{i} b^{j} a^{k}$, the parse tree is uniquely determined by $(i,j,k)$ and by the forced number of rule applications inside each $A$ and $B$.

Therefore, the claim “the given grammar is ambiguous” is not supported: the grammar is unambiguous.

Footnotes

1. Wikipedia — Context-free grammar productions and language generation (rules like $A \to aA \mid \varepsilon$ yield $a^*$). https://en.wikipedia.org/wiki/Regular_grammar - Covers how recursive productions with $\\varepsilon$ generate repetition languages; applicable to the behavior of $A$ and $B$ here. ↩ ↩² ↩³

2. Wikipedia — Parse tree and derivations concepts. https://en.wikipedia.org/wiki/Parse_tree - Background on parse trees (tree structure reflecting derivations). ↩