Ambiguity of the Grammar on String aab

Ambiguity of the Grammar on String aab

Verified Sources

Nov 4, 2026

We study the context-free grammar (CFG)

$S \rightarrow aS \mid aSbS \mid \varepsilon$

To prove a CFG is ambiguous on a particular string $w$ , we exhibit two distinct parse trees (equivalently, two distinct leftmost or rightmost derivations) that generate the same string $w$ . In this section we prove that the grammar is ambiguous for the specific string $w = \texttt{aab}$ .

Key idea: the nonterminal $S$ can either

“wrap” itself with a leading $a$ (via $S \Rightarrow aS$ ), or
split into two $S$ ’s separated by a $b$ (via $S \Rightarrow aSbS$ ).

Because these options can be combined in more than one structural way to produce $\texttt{aab}$ , we can construct two different derivation structures for the same terminal string.

We will explicitly construct:

two different leftmost derivations of $\texttt{aab}$ , and
the corresponding two different parse trees.

Ambiguity
Parse tree
Leftmost derivation
Rightmost derivation

Ambiguous Grammars (CFG) — Parse Trees and Derivations

Goal

Show that there exist two different derivations that both produce $\texttt{aab}$ . Since ambiguity can be witnessed by parse trees, it suffices to show two different parse trees for $\texttt{aab}$ .

Construct two different leftmost derivations for S ⇒* aab

1
Step 1
Start with $S$ . Use $S \Rightarrow aSbS$ . Then choose left $S \Rightarrow aS$ and then $S \Rightarrow \varepsilon$ to make the left side generate the single terminal $a$ . Choose the rightmost $S \Rightarrow \varepsilon$ so it contributes nothing after the $b$ .
2
Step 2
One leftmost derivation is:

$\begin{aligned} S &\Rightarrow aSbS\\ &\Rightarrow a(aS)bS \quad (\text{expand the leftmost } S\text{ using } S\Rightarrow aS)\\ &\Rightarrow aa bS \quad (\text{expand that leftmost } S\Rightarrow \varepsilon)\\ &\Rightarrow aab \quad (\text{expand the remaining } S\Rightarrow \varepsilon) \end{aligned}$
3
Step 3
Alternatively, begin with $S \Rightarrow aS$ to produce the first $a$ . Then expand that inner $S$ using $S \Rightarrow aSbS$ , with the left inner $S \Rightarrow \varepsilon$ and the right inner $S \Rightarrow \varepsilon$ so the remaining terminals become exactly $ab$ after the first $a$ .
4
Step 4
A different leftmost derivation is:

$\begin{aligned} S &\Rightarrow aS\\ &\Rightarrow aaSbS \quad (\text{expand the leftmost } S\text{ using } S\Rightarrow aSbS)\\ &\Rightarrow aa bS \quad (\text{expand leftmost } S\Rightarrow \varepsilon)\\ &\Rightarrow aab \quad (\text{expand remaining } S\Rightarrow \varepsilon) \end{aligned}$

Why these derivations are different (structural witness)

Both derivations generate the same terminal string $\texttt{aab}$ , but they do so with different top-level rule usage positions, which yields different parse trees.

Derivation 1 uses the rule $S \Rightarrow aSbS$ at the root, immediately creating the $b$ in the middle.
Derivation 2 uses the rule $S \Rightarrow aS$ at the root, and only later uses $S \Rightarrow aSbS$ inside the derivation.

This difference changes the parse tree structure, even though the final yield of terminals is the same.

Parse trees for $w=\texttt{aab}$

Parse tree A (corresponds to Derivation 1)

Using the root production $S \Rightarrow aSbS$ :

Root: $S$
Root expands to: $a\; S\; b\; S$
Left $S \Rightarrow aS \Rightarrow a\varepsilon$
Right $S \Rightarrow \varepsilon$

So the frontier (leaf terminals) is $a\;a\;b$ .

Parse tree B (corresponds to Derivation 2)

Using $S \Rightarrow aS$ at the root, then $S \Rightarrow aSbS$ inside:

Root: $S \Rightarrow aS$
Inner $S \Rightarrow aSbS$
Left inner $S \Rightarrow \varepsilon$
Right inner $S \Rightarrow \varepsilon$

Frontier terminals again become $a\;a\;b$ .

Parse-tree ambiguity
Frontier
Production
Start symbol

Common pitfalls and how to avoid them

Where ambiguity arises in this grammar

Option 1: Use aSbS immediately

Root choice

Root creates the middle $b$ structure right away, then the two $S$ ’s generate the $a$ and the empty tail."

Option 2: Use aS first

Root choice

Root delays creating the $b$ by adding an initial $a$ , then uses aSbS one level down to place the $b$ ."

Both strategies generate aab

Yield check

After appropriate substitutions of $S \Rightarrow \varepsilon$ on the remaining nonterminals, both parse trees have the same frontier aab."

Knowledge Check

Question 1 of 3

Q1Single choice

Which pair of productions can be combined to generate at least one terminal 'b' in this grammar?

The production aSbS is the only one that contains terminal b

The production aS is the only one that contains terminal b

Both aS and ε directly contain terminal b

None of the productions contains terminal b

Explore Related Topics

Check Whether the Given Grammar Is CLR(1)

Semantic Actions in Context-Free Grammars: Deriving Output for Input `aadbd`

Language Theory: Interpreting the Regular Expression $(a \mid b)^*$

Browse all research articles