Question:medium

Which of the following grammars is/are ambiguous?

Show Hint

Look for a string with more than one distinct parse tree; grammar B (no operator precedence between + and *) and grammar C (mixed left and right recursion on the same symbol) both admit this, while A and D generate every string uniquely.
Updated On: Aug 3, 2026
  • π‘†β†’π‘Žπ‘†π‘ | πœ–
  • 𝐸→𝐸+ 𝐸 | πΈβˆ—πΈ | 𝑖𝑑
  • π‘†β†’π‘Žπ‘† | π‘†π‘Ž | πœ–
  • π‘†β†’π‘Žπ‘† | πœ–
Show Solution

The Correct Option is B, C

Solution and Explanation

An easy trick to test ambiguity for small grammars: pick a short string in the language and try to draw more than one distinct parse tree (or leftmost derivation) for it.

Grammar A: \(S \to aSb \mid \epsilon\) generates matched nested pairs like \(ab\), \(aabb\), and so on. Every \(a\) must be matched with a \(b\) in strict nested order, leaving no freedom in the derivation - only one parse tree per string. Unambiguous.

Grammar B: \(E \to E+E \mid E*E \mid id\) is the textbook example of an ambiguous expression grammar. For \(id+id*id\), applying \(+\) at the top level gives one tree, applying \(*\) at the top level gives a different tree, and since the grammar sets no precedence between \(+\) and \(*\), both are equally valid derivations of the same string. Two distinct trees means ambiguous.

Grammar C: \(S \to aS \mid Sa \mid \epsilon\) generates \(a^n\), the same language as grammar D, but recursion is allowed on both the left (\(Sa\)) and the right (\(aS\)) simultaneously. For a string such as \(aa\), the two occurrences of \(a\) can be attached in more than one structurally distinct order, so more than one parse tree exists for the same string. Ambiguous.

Grammar D: \(S \to aS \mid \epsilon\) recurses only on the right, so each \(a^n\) has one and only one derivation. Unambiguous.

Result: The ambiguous grammars are B and C.

Was this answer helpful?
0

Top Questions on Context Free Languages and Pushdown Automata

Questions Asked in GATE CS exam