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. This set gives you 11 exact published bank MCQs, each linked to its live solved page and followed by an explanation. KnowledgeGate has more than 40 published questions in this subtopic. Attempt each item 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 a precedence-aware grammar can remove the collision. Ambiguity in one grammar does not prove inherent ambiguity.
A contrast is L = {a^i b^j c^k | i = j or j = k, i,j,k >= 1}. Its overlap strings a^n b^n c^n satisfy both conditions, but two derivations in one chosen grammar do not prove inherent ambiguity. Below, name the answer, find a reliable witness, and show both structures.
Definitions, recursion and derivation language
Q1. Definition of an ambiguous grammar
Bihar STET 2025. Open the live 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 live 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 live 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 live solved question.
The language of all non-null strings of a's can be defined by a context free grammar as follow : \(S \rightarrow a \: S \mid S\: a \mid a\) The word 𝑎3 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 live 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 live 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 live solved question.
Given the following grammars
G₁
S → AB / aaB
A → aA / ε
B → bB / ε
G₂
S → A / B
A → aAb / ab
B → abB / ε
(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 live 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 live 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 live solved question.
Which of the following grammars is(are) ambiguous?
(A) \(s \rightarrow ss \mid asb \mid bsa \mid \lambda\)
(B) \(s \rightarrow asbs \mid bsas \mid \lambda\)
(C) \(s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes 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 live 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). This tests grammar-level precedence, not inherent ambiguity directly.
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 |
|
Study-only check: at 9-11, move to mixed CFG questions; at 6-8, redo every witness without notes; at 0-5, return to derivations and parse trees. This is practice guidance, not a selection claim.
Continue with Context-Free Grammar MCQs or the GATE CS category. Use GATE Guidance by Sanchit Sir for structured Compiler Design and the GATE Test Series for timed mixed practice.
