7.2 Ambiguity in Context-Free Grammars & Inherently Ambiguous Languages

Back to DBMS Notes

📚Module 01Topic 1.1⏱️20 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The Linguistic Double-Meaning

In human languages, a single sentence can often be interpreted in two completely different ways because the underlying sentence structure is ambiguous.

Consider the famous linguistic paradox:

"I saw the man with the telescope."

Does this mean:

1. Meaning A: I looked through my telescope and observed a man? (The prepositional phrase attaches to the verb "saw".)
2. Meaning B: I observed a man who was carrying a telescope? (The prepositional phrase attaches to the noun "man".)

In casual human conversation, humans use contextual cues, body language, and shared background knowledge to resolve this ambiguity.

🍳 The Everyday Analogy: The Ambiguous Recipe

Imagine a cooking instruction written as:

"Chop the onions and carrots in the bowl."

• Interpretation 1: Take the onions and carrots that are already sitting inside the bowl, and chop them.
• Interpretation 2: Take whole onions and whole carrots, and chop them so that the resulting pieces land into the bowl.

If an automated industrial cooking robot executes this recipe, it will freeze or produce unpredictable results unless the grammar of the instruction admits strictly one structural interpretation.

💻 Bridging to Computer Science

In computer science, compilers cannot tolerate grammatical ambiguity. A compiler relies on the parse tree to determine the operational semantics (meaning) of code:

If an expression grammar parses $2 + 3 * 4$ into two different trees:

• Tree 1: Evaluates as $(2 + 3) * 4 = 20$.
• Tree 2: Evaluates as $2 + (3 * 4) = 14$.

A programmer's bank account calculation could yield two totally different numerical results depending on which parse tree the compiler chose!

A Context-Free Grammar $G$ is called ambiguous if it allows at least one string to have two or more distinct parse trees (or equivalently, two or more distinct Leftmost Derivations).

Furthermore, theoretical computer science reveals a deeper phenomenon: there exist certain Context-Free Languages for which no unambiguous grammar can ever be constructed. These are called Inherently Ambiguous Languages.

---

📑Table of Contents

• ⚖️ Formal Definition of Grammar Ambiguity
• 🧮 Classic Ambiguity Case Study: Arithmetic Expressions
  • Derivation Path A (Precedence: Multiplications First)
  • Derivation Path B (Precedence: Addition First)
• 🛠️ Disambiguation Engineering: Stratified Grammar Design
  • The Disambiguated Grammar
• ⚠️ The Dangling-Else Problem
  • Resolving the Dangling-Else in Compilers
• 🌌 Inherently Ambiguous Languages
  • The Canonical Inherently Ambiguous Language
• 🚫 The Undecidability of Ambiguity
• 🏭 Real-World Production Context: Parser Conflict Resolution
  • Modern Industrial Implementations
• 📐 Numerical Applications & Worked Examples
  • Problem 1: Systematic Ambiguity Verification with Dual Trees
  • Problem 2: Disambiguating a Prefix Expression Grammar
  • Problem 3: Proving Ambiguity in Union of Overlapping Context-Free Sets
• 🎯 Exam & Interview Pitfall Check

---

⚖️ Formal Definition of Grammar Ambiguity

A Context-Free Grammar $G = (V, T, P, S)$ is said to be ambiguous if there exists at least one string $w \in L(G)$ that satisfies any of the following mutually equivalent conditions:

The 3 Equivalent Definitions of CFG Ambiguity

Three distinct mathematical perspectives defining identical syntactic instability

Geometric Perspective

Multiple Parse Trees

🌳

Dominant Architecture / DomainConcrete Syntax Trees

• •There exists at least one string w ∈ L(G) that has TWO OR MORE distinct parse trees.
• •The hierarchical attachment of interior variable nodes differs.
• •Directly creates conflicting parent-child semantic bindings.

"Two distinct tree shapes for one single input string."

Derivational Perspective

Multiple Leftmost Derivations

👈

Dominant Architecture / DomainTop-Down Execution Traces

• •There exists at least one string w ∈ L(G) that has TWO OR MORE distinct Leftmost Derivations (LMDs).
• •At some derivation step, two different production choices are made for the leftmost variable.
• •Directly causes shift/reduce or reduce/reduce parser conflicts.

"Two different decision paths when expanding from left to right."

Crucial Equivalence:
A string $w$ has $\ge 2$ parse trees $\iff$ $w$ has $\ge 2$ Leftmost Derivations (LMDs) $\iff$ $w$ has $\ge 2$ Rightmost Derivations (RMDs).

The Derivation Trap

Having two different derivations for a string does NOT make a grammar ambiguous if one derivation is an LMD and the other is an RMD! Ambiguity requires two different LMDs (or two different RMDs, or two different parse trees) for the same string.

---

🧮 Classic Ambiguity Case Study: Arithmetic Expressions

The most famous textbook and compiler example of an ambiguous grammar is the unconstrained expression grammar:

$E \longrightarrow E + E \quad \mid \quad E * E \quad \mid \quad \mathbf{id}$

Let us test the target string:

$w = \mathbf{id} + \mathbf{id} * \mathbf{id}$

Derivation Path A (Precedence: Multiplications First)

Here, the + is applied at the root, making * deeper in the tree:

$$\begin{aligned} \underline{E} &\Longrightarrow_{lm} \underline{E} + E && (\text{applied } E \to E + E) \\ &\Longrightarrow_{lm} \mathbf{id} + \underline{E} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \underline{E} * E && (\text{applied } E \to E * E) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \underline{E} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \end{aligned}$$

• Semantic Evaluation: The subexpression $\mathbf{id} * \mathbf{id}$ is grouped together first. For $2 + 3 * 4$, this evaluates to $2 + 12 = 14$.

Derivation Path B (Precedence: Addition First)

Here, the * is applied at the root, making + deeper in the tree:

$$\begin{aligned} \underline{E} &\Longrightarrow_{lm} \underline{E} * E && (\text{applied } E \to E * E) \\ &\Longrightarrow_{lm} \underline{E} + E * E && (\text{applied } E \to E + E) \\ &\Longrightarrow_{lm} \mathbf{id} + \underline{E} * E && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \underline{E} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \end{aligned}$$

• Semantic Evaluation: The subexpression $\mathbf{id} + \mathbf{id}$ is grouped together first. For $2 + 3 * 4$, this evaluates to $(2 + 3) * 4 = 20$.

Because the string $\mathbf{id} + \mathbf{id} * \mathbf{id}$ has two distinct parse trees, the grammar is ambiguous.

---

🛠️ Disambiguation Engineering: Stratified Grammar Design

In compiler design, how do software engineers fix an ambiguous grammar? We rewrite the grammar by explicitly enforcing two structural rules:

1. Operator Precedence: Operations that bind tighter (*, /) must appear lower in the parse tree (further away from the start symbol).
2. Associativity: Left-associative operators (+, -, *) must use left-recursive productions ($A \to A \alpha \mid \beta$).

The 3-Tier Stratified Expression Architecture

Hierarchical variable layering enforcing operator precedence and left-associativity

Level 1: Lowest Precedence

Expression Variable (E)

➕

Handles addition and subtraction. Left-recursive: E → E + T | T guarantees left-to-right evaluation.

E → E + T | TLeft-associative +Lowest binding strength

↓Falls Through to Terms

Level 2: Higher Precedence

Term Variable (T)

✖️

Handles multiplication and division. Left-recursive: T → T * F | F binds tighter than addition.

T → T * F | FLeft-associative *Higher binding strength

↓Falls Through to Factors

Level 3: Highest Precedence

Factor Variable (F)

🧱

Handles atomic operands, identifiers, and explicit parentheses overrides.

F → ( E ) | idParentheses reset hierarchy to Level 1Atomic building blocks

The Disambiguated Grammar

$$\begin{aligned} E &\longrightarrow E + T \quad \mid \quad T \\ T &\longrightarrow T * F \quad \mid \quad F \\ F &\longrightarrow ( E ) \quad \mid \quad \mathbf{id} \end{aligned}$$

In this stratified grammar, for $w = \mathbf{id} + \mathbf{id} * \mathbf{id}$:

• The only valid LMD forces $E \Longrightarrow E + T \Longrightarrow T + T \Longrightarrow F + T \Longrightarrow \mathbf{id} + T \Longrightarrow \mathbf{id} + T * F \dots$
• The multiplication must attach inside the term $T$, forcing it lower down in the parse tree.
• There is strictly one unique parse tree. The grammar is completely unambiguous!

---

⚠️ The Dangling-Else Problem

A legendary ambiguity problem in real-world programming languages (such as C, C++, Java, and Pascal) is the Dangling-Else dilemma.

Consider the conditional grammar:

$$\begin{aligned} S &\longrightarrow \mathbf{if} \; C \; \mathbf{then} \; S \\ &\mid \quad \mathbf{if} \; C \; \mathbf{then} \; S \; \mathbf{else} \; S \\ &\mid \quad \mathbf{other} \end{aligned}$$

Now inspect the nested conditional statement:

$\mathbf{if} \; C_1 \; \mathbf{then} \; \mathbf{if} \; C_2 \; \mathbf{then} \; S_1 \; \mathbf{else} \; S_2$

Which if does the else belong to?

The Dangling-Else Structural Conflict

Two competing attachments for a single else clause

Interpretation A (Inner Attachment)

Closest-If Binding (Standard)

🎯

Dominant Architecture / DomainStandard Language Semantics (C, Java, Python)

• •The 'else' attaches to the nearest preceding 'if' (if C₂).
• •If C₁ is true and C₂ is false, S₂ executes.
• •If C₁ is false, nothing executes.
• •Matches programmer expectation in modern languages.

"Match each else with the closest unmatched then."

Interpretation B (Outer Attachment)

Outer-If Binding (Erroneous)

⚠️

Dominant Architecture / DomainAlternative Parse Tree

• •The 'else' attaches to the outermost 'if' (if C₁).
• •If C₁ is true and C₂ is false, nothing executes.
• •If C₁ is false, S₂ executes.
• •Fundamentally alters program control-flow.

"A silent semantic divergence causing critical runtime bugs."

Resolving the Dangling-Else in Compilers

To disambiguate this grammar, compilers partition statements into Matched Statements (statements where every then has an explicit else) and Open / Unmatched Statements:

$$\begin{aligned} \text{Stmt} &\longrightarrow \text{MatchedStmt} \quad \mid \quad \text{OpenStmt} \\ \text{MatchedStmt} &\longrightarrow \mathbf{if} \; C \; \mathbf{then} \; \text{MatchedStmt} \; \mathbf{else} \; \text{MatchedStmt} \quad \mid \quad \mathbf{other} \\ \text{OpenStmt} &\longrightarrow \mathbf{if} \; C \; \mathbf{then} \; \text{Stmt} \\ &\mid \quad \mathbf{if} \; C \; \mathbf{then} \; \text{MatchedStmt} \; \mathbf{else} \; \text{OpenStmt} \end{aligned}$$

By forbidding an unmatched if inside the then clause of an if-else pair, this grammar enforces that an else must always bind to the closest inner if, making the grammar completely unambiguous.

---

🌌 Inherently Ambiguous Languages

A common question among computer scientists is: Can every ambiguous grammar be rewritten into an equivalent unambiguous grammar?

The surprising and profound answer is NO.

There exist certain formal languages whose intrinsic combinatorial structure makes it impossible to design an unambiguous grammar.

Definition: A Context-Free Language $L$ is said to be Inherently Ambiguous if every possible Context-Free Grammar that generates $L$ is ambiguous.

Architecture Flow

The Inherently Ambiguous Language Architecture

Why non-deterministic overlapping subsets force multiple derivation paths

🅰️Sub-Language 1

L₁ = { aⁱ bⁱ cᵏ }

Enforces equal counts of a's and b's (i = j), arbitrary c's.

→

Language Union

🔀Composite Target

L = L₁ ∪ L₂

L = { aⁱ bʲ cᵏ | i = j OR j = k }. CFG must cover both constraints.

→

Structural Overlap

🅱️Sub-Language 2

L₂ = { aⁱ bʲ cʲ }

Enforces equal counts of b's and c's (j = k), arbitrary a's.

→

Collision Point

💥Fatal Ambiguity

Intersection: aⁿ bⁿ cⁿ

Strings with i = j = k can be generated through both L₁ and L₂ branches, guaranteeing ≥ 2 distinct parse trees in ANY grammar.

The Canonical Inherently Ambiguous Language

Consider the language:

$L = \{ a^i b^j c^k \mid i = j \quad \text{or} \quad j = k; \quad i, j, k \ge 1 \}$

1. $L$ is a Context-Free Language because it is the union of two CFLs:
   • $L_1 = \{a^i b^i c^k \mid i \ge 1, k \ge 1\}$ (generated by $S_1 \to A C, A \to aAb \mid ab, C \to cC \mid c$).
   • $L_2 = \{a^i b^k c^k \mid i \ge 1, k \ge 1\}$ (generated by $S_2 \to A B, A \to aA \mid a, B \to bBc \mid bc$).
2. A straightforward grammar for $L$ is $S \to S_1 \mid S_2$.
3. Now consider any string where $i = j = k = n$, such as:

$w = a^n b^n c^n \quad (\text{e.g., } a^2 b^2 c^2 = aabbcc)$

• String $w$ belongs to $L_1$ (since $i = j = 2$). It can be derived via the $S_1$ branch.
• String $w$ also belongs to $L_2$ (since $j = k = 2$). It can be derived via the $S_2$ branch.
• In 1962, mathematicians proved that in any possible CFG generating $L$, the two production channels must overlap on strings with $i = j = k$. Therefore, every string of the form $a^n b^n c^n$ must have at least two distinct parse trees in any CFG for $L$.

4. Thus, $L = \{a^i b^j c^k \mid i = j \text{ or } j = k\}$ is Inherently Ambiguous.

---

🚫 The Undecidability of Ambiguity

Can we write an algorithm or compiler tool that takes an arbitrary CFG $G$ and automatically tells us: "YES, this grammar is ambiguous" or "NO, this grammar is unambiguous"?

The Ambiguity Undecidability Theorem:
The problem of determining whether an arbitrary Context-Free Grammar $G$ is ambiguous is fundamentally UNDECIDABLE.

Furthermore:

• Determining whether an arbitrary Context-Free Language is inherently ambiguous is undecidable.
• There exists no general algorithm that can take an arbitrary ambiguous CFG and convert it into an equivalent unambiguous CFG.
• This result is formally proven via reduction from the Post Correspondence Problem (PCP).

Because ambiguity is undecidable for general CFGs, compiler writers restrict programming language syntax to restricted, decidable deterministic subclasses: LL(k), LR(k), and LALR(1) grammars, which are guaranteed to be unambiguous by construction.

---

🏭 Real-World Production Context: Parser Conflict Resolution

In commercial software development, parser generator tools such as GNU Bison, Yacc, ANTLR, and Tree-sitter must routinely deal with grammatical ambiguity.

Architecture Flow

Production Parser Conflict Resolution Pipeline

How Yacc and Bison resolve ambiguity during LALR(1) table construction

📜Grammar File

.y Grammar Specification

Developer defines productions: expr: expr '+' expr | expr '*' expr | ID.

→

LALR State Machine

⚙️Conflict Detection

Parser Table Generator

Generates LR item sets. Ambiguity produces Shift/Reduce or Reduce/Reduce conflicts.

→

Precedence Directives

🛡️Precedence Resolution

%left & %right Declarations

Developer specifies: %left '+' '-' and %left '*' '/'. Bison chooses Shift over Reduce automatically.

→

Deterministic Table

🚀Compilation

C / C++ Parser Source

Emits high-speed O(N) deterministic parser code with zero runtime ambiguity.

Modern Industrial Implementations

1. Tree-sitter (GitHub / Neovim / VS Code): Tree-sitter uses a GLR (Generalized LR) parser. When a language grammar contains temporary syntactic ambiguity (such as C++ template syntax foo<bar>(baz) which could be a comparison or a template function call), Tree-sitter forks the parser into parallel branches and prunes invalid branches as more tokens arrive.
2. GCC & Clang (C++ Compilation): C++ is notorious for the "Most Vexing Parse" (e.g. TimeKeeper time_keeper(Timer());, which can be parsed as a variable declaration with an anonymous temporary, or as a function declaration taking a pointer to a function). Clang resolves this using contextual disambiguation rules specified in the ISO C++ standard.
3. ANTLR (Java, C#, Python): ANTLR 4 uses Adaptive LL(*) parsing (ALL(*)). Instead of failing on ambiguous choices at compile time, ANTLR evaluates lookahead dynamically at runtime using deterministic finite automata, picking the first matching alternative in the grammar specification.

---

📐 Numerical Applications & Worked Examples

Problem 1: Systematic Ambiguity Verification with Dual Trees

Problem Statement:
Consider the CFG over alphabet $\Sigma = \{a, b\}$:

$S \longrightarrow a S \quad \mid \quad a S b S \quad \mid \quad \epsilon$

Prove that this grammar is ambiguous by:

1. Finding the shortest non-trivial string that admits two distinct parse trees.
2. Constructing the two distinct Leftmost Derivations (LMDs).
3. Documenting the structural differences in the two parse trees.

Step-by-Step Solution:

Step 1: Candidate String Selection

• String $\epsilon$: Has 1 tree ($S \to \epsilon$).
• String "a": $S \to aS \to a\epsilon = a$. Unique.
• String "ab":
  • Tree 1: $S \to aS \to a(a S b S) \dots$ (produces $aab$).
  • Can "ab" be produced two ways?
    • Path A: $S \Longrightarrow a S b S \Longrightarrow a(\epsilon) b (\epsilon) = ab$.
    • Path B: Can $S \to aS$ produce $ab$? $aS \to a(b\dots)$ requires $S$ to produce $b$, but no rule begins with $b$ except $aSbS$.
• Let us test $w = \mathbf{a a b}$:

Step 2: Constructing Two Distinct LMDs for w = aab

Leftmost Derivation 1: Expand with $S \to aS$ at the root:

$$\begin{aligned} \underline{S} &\Longrightarrow_{lm} a \underline{S} && (\text{applied } S \to aS) \\ &\Longrightarrow_{lm} a a \underline{S} b S && (\text{applied } S \to aSbS) \\ &\Longrightarrow_{lm} a a \epsilon b \underline{S} && (\text{applied } S \to \epsilon) \\ &\Longrightarrow_{lm} a a b \epsilon && (\text{applied } S \to \epsilon) \\ &= \mathbf{aab} \end{aligned}$$

Leftmost Derivation 2: Expand with $S \to aSbS$ at the root:

$$\begin{aligned} \underline{S} &\Longrightarrow_{lm} a \underline{S} b S && (\text{applied } S \to aSbS) \\ &\Longrightarrow_{lm} a a \underline{S} b S && (\text{applied } S \to aS \text{ on first variable}) \\ &\Longrightarrow_{lm} a a \epsilon b \underline{S} && (\text{applied } S \to \epsilon) \\ &\Longrightarrow_{lm} a a b \epsilon && (\text{applied } S \to \epsilon) \\ &= \mathbf{aab} \end{aligned}$$

Step 3: Structural Parse Tree Contrast

• In Tree 1, the root $S$ expands via $S \to aS$. The inner $S$ is the parent of the $b$ terminal. The terminal $b$ sits at Level 2 of the tree.
• In Tree 2, the root $S$ expands via $S \to aSbS$. The root itself is the direct parent of the $b$ terminal. The terminal $b$ sits at Level 1 of the tree.

Because two distinct parse trees exist for the string $w = aab$, the grammar is ambiguous.

---

Problem 2: Disambiguating a Prefix Expression Grammar

Problem Statement:
Consider the grammar generating conditional statements:

$S \longrightarrow \mathbf{c} \; S \; S \quad \mid \quad \mathbf{a}$

Where $\mathbf{c}$ represents a binary condition connector (like cond ? x : y) and $\mathbf{a}$ represents an atomic action.

1. Show whether the grammar is ambiguous for the string $w = \mathbf{c c a a a}$.
2. If ambiguous, provide two distinct Leftmost Derivations.

Step-by-Step Solution:

Step 1: Trace Derivations on w = ccaaa

Let us attempt to derive $w$:

Attempt 1 (Left-Branching):

$$\begin{aligned} \underline{S} &\Longrightarrow \mathbf{c} \underline{S} S && (\text{rule } S \to cSS) \\ &\Longrightarrow \mathbf{c} \mathbf{c} \underline{S} S S && (\text{expand first } S \to cSS) \\ &\Longrightarrow \mathbf{c} \mathbf{c} \mathbf{a} \underline{S} S && (\text{expand } S \to a) \\ &\Longrightarrow \mathbf{c} \mathbf{c} \mathbf{a} \mathbf{a} \underline{S} && (\text{expand } S \to a) \\ &\Longrightarrow \mathbf{c} \mathbf{c} \mathbf{a} \mathbf{a} \mathbf{a} && (\text{expand } S \to a) \end{aligned}$$

Attempt 2 (Can we expand the second $S$ first?): Remember that for an LMD, we must expand the leftmost non-terminal:

• Can the first $S$ expand to $a$?
  • $S \Longrightarrow \mathbf{c} \underline{S} S \Longrightarrow \mathbf{c} \mathbf{a} \underline{S}$.
  • If $\mathbf{c} \mathbf{a} S$ is reached, any expansion of $S$ starts with $\mathbf{c}$ or $\mathbf{a}$:
    • If $S \to cSS$, string prefix is $\mathbf{c} \mathbf{a} \mathbf{c} \dots$ (does not match target $w = ccaaa$).
    • If $S \to a$, string is $\mathbf{c} \mathbf{a} \mathbf{a}$ (length 3, does not match length 5).
• Can any other production be applied at step 1?
  • The only productions are $S \to cSS$ and $S \to a$. Since $w$ starts with $c$, the root must expand to $cSS$.
  • The first symbol after $c$ in $w$ is another $c$. Therefore, the first child $S$ must expand to $cSS$.

Step 2: Polish Prefix Unambiguity Theorem

Because every operator $\mathbf{c}$ is a prefix operator with a fixed arity of 2 (Polish prefix notation), there is strictly one valid parse tree for every valid well-formed prefix expression!

Therefore, the string $w = ccaaa$ has only one unique derivation, and this prefix grammar is UNAMBIGUOUS.

---

Problem 3: Proving Ambiguity in Union of Overlapping Context-Free Sets

Problem Statement:
Let grammar $G$ have start symbol $S$ and productions:

$$\begin{aligned} S &\longrightarrow A \quad \mid \quad B \\ A &\longrightarrow 0 A 1 \quad \mid \quad 0 1 \\ B &\longrightarrow 0 B \quad \mid \quad C \\ C &\longrightarrow 1 C \quad \mid \quad 1 \end{aligned}$$

1. Identify the languages generated by variables $A$ and $B$.
2. Prove that the grammar $G$ is ambiguous by demonstrating a collision string in $L(A) \cap L(B)$.

Step-by-Step Solution:

Step 1: Language Analysis of Sub-Grammars

• Variable $A$:
  • $A \to 0A1 \mid 01$ generates equal numbers of $0$'s followed by equal numbers of $1$'s:

$L(A) = \{0^n 1^n \mid n \ge 1\} = \{01, 0011, 000111, \dots\}$

• Variable $B$:
  • $B \to 0B \mid C$ prepends an arbitrary number of $0$'s ($0^m$ for $m \ge 0$).
  • $C \to 1C \mid 1$ produces one or more $1$'s ($1^k$ for $k \ge 1$).
  • Combining them:

$L(B) = \{0^m 1^k \mid m \ge 0, k \ge 1\}$

Step 2: Identify the Collision Set

The language $L(G) = L(A) \cup L(B)$.
Notice that $L(A) \subset L(B)$, because any string of the form $0^n 1^n$ has $m = n$ and $k = n$, which is a valid string in $L(B)$!

Step 3: Demonstrate Two Distinct Parse Trees for w = 01

Consider the string $w = \mathbf{01}$:

Derivation 1 (via variable $A$):

$S \Longrightarrow_{lm} A \Longrightarrow_{lm} 01$

Derivation 2 (via variable $B$):

$S \Longrightarrow_{lm} B \Longrightarrow_{lm} 0 B \Longrightarrow_{lm} 0 C \Longrightarrow_{lm} 0 1$

• In Derivation 1, the immediate child of root $S$ is $A$.
• In Derivation 2, the immediate child of root $S$ is $B$.

Since two distinct parse trees exist for $w = 01$, grammar $G$ is ambiguous.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Is ambiguity an inherent property of a language or a property of a grammar?
  Ambiguity is primarily a property of a grammar. A given language can be generated by an ambiguous grammar, but often we can design an alternative, completely unambiguous grammar for the exact same language (e.g. arithmetic expressions). It is only when no unambiguous grammar exists for a language that we call the language itself Inherently Ambiguous.
• Can a regular language ever be inherently ambiguous?
  NO! Never! Every regular language has a unique minimal Deterministic Finite Automaton (DFA). A DFA can be converted directly into a regular grammar where every production corresponds to a deterministic state transition. Because a DFA has at most one active state transition per symbol, the resulting grammar is guaranteed to be unambiguous. Therefore, no regular language is inherently ambiguous.
• Why can't compiler generators automatically remove ambiguity?
  Because determining whether an arbitrary CFG is ambiguous is undecidable (proven via reduction from PCP). If a computer algorithm cannot even determine whether a grammar is ambiguous, it cannot be expected to automatically fix it. Compilers rely on explicit developer annotations (such as %left, %right, and %nonassoc directives in Bison).

Common Interview Traps

• Trap: Equating Number of Derivations with Number of Parse Trees:
  A string can have multiple derivations simply because different non-terminals were expanded in different chronological orders (e.g. mixing leftmost and rightmost steps). Multiple derivations prove ambiguity only if they are both Leftmost Derivations (or both Rightmost Derivations).
• Trap: Believing All Ambiguity Leads to Compiler Errors:
  Ambiguous grammars do not necessarily cause compiler crashes; rather, they lead to semantic miscompilations. If a compiler silently picks one parse tree over another without the programmer realizing it, the compiled binary will perform the wrong calculation at runtime.
• Trap: Confusing Non-Deterministic CFLs with Inherently Ambiguous CFLs:
  While all inherently ambiguous CFLs require non-deterministic pushdown automata (cannot be parsed by a DPDA), not all non-deterministic CFLs are inherently ambiguous! For example, the language of even palindromes $L = \{w w^R \mid w \in \{a, b\}^*\}$ is non-deterministic (requires NPDA), but it has an unambiguous grammar: $S \to aSa \mid bSb \mid \epsilon$.

---

🗺️View Complete DBMS Roadmap & Syllabus

← Previous Topic7.1 Context-Free Grammars: Parse Trees, Leftmost & Rightmost DerivationsNext Topic →7.3 Grammar Simplification & Normal Forms: Chomsky (CNF) & Greibach (GNF)