An ambiguity question is not settled by spotting recursion, or by finding a leftmost derivation and a rightmost derivation. The decisive test is whether one terminal string has two distinct parse trees, equivalently two distinct leftmost derivations or two distinct rightmost derivations. The 11 questions below are previous-year MCQs from GATE, UGC NET, ISRO and state papers, and every one of them turns on that single test. Attempt each before reading the answer. Whenever a grammar may be ambiguous, write a small witness string and construct both competing structures. If derivations and parse trees need revision first, read Context-Free Grammars and Pushdown Automata.
Separate ambiguous grammar from inherently ambiguous language
A CFG is ambiguous if one string has more than one parse tree. A context-free language is inherently ambiguous only if every CFG generating it is ambiguous.
For E -> E + E | E * E | id, id + id * id has the structures (id + id) * id and id + (id * id). This grammar is ambiguous, but splitting it into separate levels for + and * removes the collision, which is what Ambiguous Grammars, Precedence and Associativity for GATE works through. Ambiguity in one grammar does not prove inherent ambiguity.
The standard example of a language that really is inherently ambiguous is L = {a^i b^j c^k | i = j or j = k, i,j,k >= 1}. Any grammar for it must cover the strings whose a-block matches their b-block and the strings whose b-block matches their c-block, and the overlap strings a^n b^n c^n belong to both families at once. However the productions are arranged, some overlap string picks up one structure from each family, so no unambiguous grammar for this language exists. The full proof runs through Ogden's lemma.
Keep the direction of the argument straight. Two derivations of one string prove that the grammar in front of you is ambiguous, and nothing more. Inherent ambiguity is a claim about every grammar for the language at once. Exam questions almost always ask the first kind, and each answer below is settled the same way: name a witness string, then show its two structures.
Definitions, recursion and derivation language
Q1. Definition of an ambiguous grammar
Bihar STET 2025. Open the solved question.
A grammar that produces more than one parse tree for the same sentence is called:
(a) Contiguous
(b) Ambiguous
(c) Unambiguous
(d) Regular
Answer: (b) Ambiguous. One witness with two parse trees is enough. Equivalently, show two leftmost or two rightmost derivations of the same string. Recursion alone proves nothing.
Q2. Both left and right recursion
GATE 1999. Open the solved question.
A grammar that is both left and right recursive for a non-terminal is
(a) Ambiguous
(b) Unambiguous
(c) Information is not sufficient to decide whether it is ambiguous or Unambiguous.
(d) None of the above
Answer: (a) Ambiguous. For S -> Sa | aS | a, aa follows S=>Sa=>aa and S=>aS=>aa, giving distinct structures.
Q3. Unique does not mean identical expansion order
GATE 2001. Open the solved question.
Which of the following statements is false?
(a) An unambiguous grammar has the same leftmost and rightmost derivation
(b) An LL(1) parser is a top-down parser
(c) LALR parsing is more powerful than SLR parsing
(d) An ambiguous grammar can never be LR(k) for any k
Answer: (a). An unambiguous grammar has one leftmost and one rightmost derivation, but their expansion orders differ. LL is top-down, LALR is broader than SLR, and LR grammars are unambiguous.
Count parse trees and expose operator ambiguity
Q4. Four parse trees for a^3
UGC NET 2015. Open the solved question.
The language of all non-null strings of a's can be defined by a context free grammar as follow : S → a S | S a | a. The word a³ can be generated by ______ different trees.
(a) Two
(b) Three
(c) Four
(d) Five
Answer: (c) Four. The sequences are left-left S=>aS=>aaS=>aaa; left-right S=>aS=>aSa=>aaa; right-left S=>Sa=>aSa=>aaa; right-right S=>Sa=>Saa=>aaa. Each attachment differs, but every yield is aaa.
Q5. Two structures for one arithmetic expression
ISRO 2023. Open the solved question.
Consider the context-free grammar G below for arithmetic expressions : E→E+E|E×E| id Which of the following statements is TRUE:
(a) The string "id +id×id " has no parse tree according to G
(b) The string "id +id× id " has only one parse tree according to G
(c) The string "id +id×id " has exactly two parse trees according to G
(d) The string "id +id×id " has more than two parse trees according to G
Answer: (c). A root E -> E × E gives (id + id) × id; a root E -> E + E gives id + (id × id). No precedence rule excludes either structure, and there are exactly two.
Classify paired grammars with explicit witness strings
Q6. Recursion in G1 and a collision in G2
UGC NET 2018. Open the solved question.
Consider the following two grammars
G₁
S → SbS / a
G₂
S → aB / ab
A → AB / a
B → Abb / b
Which of the following option is correct?
(a) Only G₁ is ambiguous
(b) Only G₂ is ambiguous
(c) Both G₁ and G₂ are ambiguous
(d) Both G₁ and G₂ are not ambiguous
Answer: (c) Both. In G₁, ababa groups as (a b a) b a or a b (a b a). In G₂, ab follows S=>ab and S=>aB=>ab.
Q7. Two collisions in two grammars
UGC NET 2015. Open the solved question.
Given the following grammars
G₁
S → AB / aaB
A → aA / ε
B → bB / ε
G₂
S → A / B
A → aAb / ab
B → abB / ε
Which of the following is correct?
(a) G₁ is ambiguous and G₂ is unambiguous grammars
(b) G₁ is unambiguous and G₂ is ambiguous grammars
(c) Both G₁ and G₂ are ambiguous grammars
(d) Both G₁ and G₂ are unambiguous grammars
Answer: (c). In G₁, aa follows S=>aaB=>aa, or S=>AB=>aa with A=>aA=>aaA=>aa and B=>ε. In G₂, ab follows S=>A=>ab or S=>B=>abB=>ab. One witness per grammar is enough.
Ambiguity as a parsing obstacle and a statement test
Q8. Why a predictive parser cannot choose uniquely
UGC NET 2018. Open the solved question.
The grammar S → (S) | SS | ε is not suitable for predictive parsing because the grammar is
(a) Right Recursive Grammar
(b) Left Recursive Grammar
(c) Ambiguous Grammar
(d) Operator Grammar
Answer: (c) Ambiguous Grammar. The witness () follows S=>(S)=>() and S=>SS=>(S)S=>(), with the inner and trailing S becoming ε. These competing structures block a unique predictive choice. See Parsing in Compiler Design: Top-Down and Bottom-Up Explained.
Q9. Check three statements independently
UGC NET 2017. Open the solved question.
Which of the following statements is/are TRUE?
(i) The grammar S → SS / a is ambiguous (where S is the start symbol).
(ii) The grammar S → 0S1 / 01S / ε is ambiguous (the special symbol ε represents the empty string and S is the start symbol).
(iii) The grammar (where S is the start symbol)
S → T / U
T → xSy / xy / ε
U → yT
generates a language consisting of the string yxxyy.
(a) Only (i) and (ii) are TRUE
(b) Only (i) and (iii) are TRUE
(c) Only (ii) and (iii) are TRUE
(d) All of (i), (ii) and (iii) are TRUE
Answer: (d) All three. For (i), aaa groups as (aa)a and a(aa). For (ii), 01 follows S=>0S1=>01 and S=>01S=>01. For (iii), S=>U=>yT=>yxSy=>yxxyy, with inner S=>T=>xy.
Multi-grammar detection and grammar-level precedence
Q10. Find a witness for all three grammars
UGC NET 2020. Open the solved question.
Which of the following grammars is(are) ambiguous?
(A) S → SS | aSb | bSa | λ
(B) S → aSbS | bSaS | λ
(C) S → aAB, A → bBb, B → A | λ (where λ denotes the empty string)
Choose the correct answer from the options given below:
(a) (A) and (C) Only
(b) (B) Only
(c) (B) and (C) Only
(d) (A) and (B) and (C)
Answer: (d) All three. A has S=>λ and S=>SS=>λλ. In B, S=>aSbS yields abab with ba in the first S or ab in the final S. In C, abbbb places the second bb inside the first A, or in the final B through B=>A=>bBb=>bb.
Q11. Read precedence from the non-terminal level
TPSC 2025. Open the solved question.
Given the following expression grammar:
E → E * F | F + E | F
F → F − F | id
Which of the following is true?
(a) * has higher precedence than +
(b) − has higher precedence than *
(c) + and − have the same precedence
(d) + has higher precedence than *
Answer: (b) − has higher precedence than *. F is the operand level used by E, so subtraction completes before that F enters multiplication. In id * id − id, the right operand must use F=>F−F, forcing id * (id − id). Notice that the same grammar stays ambiguous higher up: * and + both sit at the E level, so id + id * id still parses as both (id + id) * id and id + (id * id). Only the subtraction is pinned by a lower level, which is why (b) is the one precedence claim this grammar actually guarantees.
Error log, set score and next practice step
Missed questions | Likely gap | Redo |
|---|---|---|
Q1-Q3 | Definition or derivation vocabulary | The two derivations of |
Q4-Q5 | Parse structures not enumerated | Four |
Q6-Q7 | No witness string |
|
Q8-Q10 | Parser choice or ε-productions |
|
Q11 | Precedence-level confusion |
|
Score yourself out of 11. At 9 or above, move on to mixed CFG questions. At 6-8, redo every witness string without notes. At 5 or below, go back to derivations and parse trees before attempting more ambiguity questions.
Continue with Context-Free Grammar MCQs or the GATE CS category. GATE Guidance by Sanchit Sir teaches Compiler Design in order, from grammars and ambiguity through to code generation.
