Ambiguous Grammars and Inherent Ambiguity: Worked CFG Examples for GATE

Finding two derivations for one grammar does not automatically show that its language is inherently ambiguous. Worse, one leftmost derivation and one rightmost derivation may describe the same parse tree. Grammar ambiguity can be removable or inherent: id+id*id, with values 2, 3, and 4, illustrates removable ambiguity, while the classic language L = {a^i b^j c^k | i = j or j = k, i,j,k >= 1} illustrates inherent ambiguity. For grammar notation, derivation basics, and the wider CFG toolkit, use Grammar and CFG in Compiler Design. The dedicated ambiguity task separates a witness for one grammar, a grammar repair, and the universal claim of inherent ambiguity.

Ambiguous grammar, unambiguous language, and inherently ambiguous language

A context-free grammar is ambiguous if at least one terminal string has two distinct parse trees. Prove it with two distinct leftmost derivations or two distinct rightmost derivations of that string. One of each is not enough, because every parse tree has both.

Ambiguity is a property of a particular grammar. A language is inherently ambiguous only when every CFG that generates it is ambiguous. One ambiguous grammar therefore does not prove inherent ambiguity.

The witness rules are decisive:

• One string with two parse trees proves that a grammar is ambiguous.

• One unambiguous CFG for a language proves that the language is not inherently ambiguous.

• Failing to find a second tree proves neither claim.

Worked example: two parses for id+id*id

Take the grammar E -> E + E | E * E | id. Let the three operands be id1 = 2, id2 = 3, and id3 = 4.

The first leftmost derivation is:

E => E + E => id + E => id + E * E => id + id * E => id + id * id

The root operator is +, so this tree means 2 + (3 * 4). Multiplication gives 3 * 4 = 12, then addition gives 2 + 12 = 14.

The second leftmost derivation is:

E => E * E => E + E * E => id + E * E => id + id * E => id + id * id

Here the root operator is *, so the grouping is (2 + 3) * 4. Addition gives 2 + 3 = 5, then multiplication gives 5 * 4 = 20.

The leaf sequence is identical, but the roots differ. These distinct leftmost derivations prove the grammar ambiguous.

Removing ambiguity with precedence and associativity

Replace the expression grammar with:

• E -> E + T | T

• T -> T * F | F

• F -> id | (E)

Multiplication is nested at the T level, so it binds more tightly than addition. Left recursion in E and T makes repeated operators left-associative.

Now derive the same token string:

E => E + T => T + T => F + T => id + T => id + T * F => id + F * F => id + id * F => id + id * id

With the same values, the grammar selects 2 + (3 * 4) = 2 + 12 = 14. It still generates the unparenthesised terminal string id+id*id, but gives it the intended parse. Ambiguity must be settled before deterministic predictive parsing because an LL(1) table needs at most one production choice in each cell. Removing left recursion alone does not, by itself, remove ambiguity.

Inherent ambiguity: the classic union language and aabbcc

Consider the standard inherently ambiguous context-free language:

L = {a^i b^j c^k | i = j or j = k, i,j,k >= 1}

Split it into L1 = {a^n b^n c^m | n,m >= 1} and L2 = {a^m b^n c^n | m,n >= 1}. Their intersection contains every string a^n b^n c^n. For n = 2, that string is aabbcc.

One union grammar is S -> AC | DB, with A -> aAb | ab, C -> cC | c, D -> aD | a, and B -> bBc | bc. The first branch derives the string as:

S => AC => aAbC => aabbC => aabbcC => aabbcc

The second branch derives it as:

S => DB => aDB => aaB => aabBc => aabbcc

These routes prove only that this union grammar is ambiguous. They show the overlap, but not that every CFG for L is ambiguous. The stronger result is a theorem: L is inherently ambiguous, so no unambiguous CFG generates it. The two branch derivations explain the overlap; they are not a proof of that universal result. Use Formal Grammar and Chomsky Hierarchy for GATE for tuple definitions and production-class classification; ambiguity questions instead ask what a witness does and does not establish.

A proof checklist for ambiguity questions

Use this decision sequence:

1. Identify whether the question asks about one grammar or an entire language.

2. Choose a short candidate terminal string.

3. Keep the convention fixed: compare leftmost with leftmost, or rightmost with rightmost.

4. Compare parse-tree roots or the key production choices.

5. State exactly what the witness proves.

For the expression grammar, root + versus root * proves ambiguity. In the precedence grammar, the only valid root for id+id*id is the top-level +. Yet one checked string does not prove the whole grammar unambiguous.

Inherent ambiguity carries a stronger burden. One witness proves a grammar ambiguous, but the language claim is universal over all CFGs. In an objective question, use a known theorem or an explicit unambiguous alternative grammar instead of trying derivations indefinitely.

Traps that cost marks

An ambiguous grammar cannot be LL(1), and it cannot be LR(k) for any fixed k. The same language may still have a different unambiguous grammar suitable for deterministic parsing. Keep practising that distinction with Parsing MCQs: Top-Down and Bottom-Up.

How GATE-style questions test the distinction

A GATE-style item may ask you to select an ambiguous grammar, find a string with two leftmost derivations, choose the parse imposed by precedence, separate a grammar claim from a language claim, or recognise the classic inherently ambiguous union language.

For a 30-second expression check, scan for E -> E op E, try three operands, compare possible root operators, and calculate both groupings. Here that is 2 + (3 * 4) = 14 against (2 + 3) * 4 = 20.

For the wider subject route, use GATE CS Exam Preparation to place grammar and parsing inside your study plan.

Ambiguity and inherent ambiguity: the short version and next step

Two parse trees for one terminal string make a grammar ambiguous. Ordinary ambiguity can sometimes be removed by supplying another unambiguous grammar, and operator precedence and associativity must be encoded in that grammar's structure. An inherently ambiguous language is different: it has no unambiguous CFG at all.

Now reproduce both leftmost derivations of id+id*id, redraw the precedence grammar, and explain in one sentence why the two aabbcc routes do not prove the universal claim by themselves. Check that your values are 14 and 20. Use GATE Guidance by Sanchit Sir for a sequenced Compiler Design route, then move to timed practice after the concept is stable.