Back to the 2023 paper

Module 2: Context-Free Languages (CFL) and PDA

20232m

A given grammar is called ambiguous if:

(i) two or more productions have the same non-terminal on LHS
(ii) a derivation tree has more than one associated sentence
(iii) there exists a sentence with more than one derivation tree
(iv) brackets are not present in the grammar

Worked SolutionAI Assisted

Answer

Correct Option: (iii) there exists a sentence with more than one derivation tree

Explanation

Ambiguous Grammar: Grammar GG is ambiguous iff there exists a string w∈L(G)w \in L(G) that has two or more distinct derivation trees (or equivalently two distinct leftmost / rightmost derivations).

  • (i) “two productions have same LHS” → false; e.g., S→a∣bS \rightarrow a \mid b has same LHS but not ambiguous (each string one tree).
  • (ii) “derivation tree has more than one sentence” — every tree yields exactly one sentence (its yield), false.
  • (iii) True — definition of ambiguity: ∃w:∣{parse trees for w}∣≥2\exists w: |\{ \text{parse trees for }w\}| \ge 2.
  • (iv) “brackets not present” — irrelevant.

Example ambiguous: S→S+S∣S∗S∣aS \rightarrow S+S \mid S*S \mid a; string a+a∗aa+a*a has two trees (different precedence).

Final Answer

Ambiguous iff some sentence has ≥2 parse trees → Option (iii).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.