Skip to content
Mon, Oct 12, 2026 / Ideas for a clearer worldINDEPENDENT INSIGHTS · PRACTICAL TOOLS · EXPLAINERS
Sign in
EXPLOREArtificial IntelligencePersonal FinancePythonStartupsMechanical EngineeringDigital MarketingCybersecurity
Theory of Computation / August 14, 2021

Ambiguity in Context-Free Grammars

If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is called an ambiguous grammar. There exist multiple right-most or left-most derivations for some string generated from that grammar.ContentsProblemSolution Problem Check whether the grammar G with production rules − X → X+X | X*X |X| a is ambiguous or not. Solution Let’s […]

By · August 14, 2021 · 1 min read

If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is called an ambiguous grammar. There exist multiple right-most or left-most derivations for some string generated from that grammar.

Contents

Problem

Check whether the grammar G with production rules −

X → X+X | X*X |X| a

is ambiguous or not.

Solution

Let’s find out the derivation tree for the string “a+a*a”. It has two leftmost derivations.

Derivation 1 − X → X+X → a +X → a+ X*X → a+a*X → a+a*a

Parse tree 1 −

Parse Tree 1

Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

Parse tree 2 −

Parse Tree 2

Since there are two parse trees for a single string “a+a*a”, the grammar G is ambiguous.