Consider the following two grammars G₁ S → SbS / a G₂ S → aB / ab A → AB / a B…

2018

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?

  1. A.

    Only G₁ is ambiguous

  2. B.

    Only G₂ is ambiguous

  3. C.

    Both G₁ and G₂ are ambiguous

  4. D.

    Both G₁ and G₂ are not ambiguous

Attempted by 99 students.

Show answer & explanation

Correct answer: C

A context-free grammar is ambiguous exactly when some string in its language has two or more structurally distinct parse trees — equivalently, two different leftmost derivations that do not fold into the same tree. A grammar is unambiguous only if every string it generates fails this test. So ambiguity is settled either by exhibiting two such trees for some generated string (proving ambiguous), or by proving that no generated string admits two such trees (proving unambiguous) — never by how compact or self-recursive a set of productions looks.

Apply this test to G₁: S → SbS / a. The rule is self-recursive with the joining terminal 'b' sitting between two S's — the same shape as the classic ambiguous expression grammar E → E + E / id — so a string containing two or more 'b's can be grouped in more than one way. Take the string 'ababa' (three a's, two b's):

Parse tree

Derivation

Left-grouped

S ⇒ SbS ⇒ (SbS)bS ⇒ (a b a) b a

Right-grouped

S ⇒ SbS ⇒ Sb(SbS) ⇒ a b (a b a)

Both derivations end at the identical string 'ababa', but the inner SbS nesting sits on opposite sides in the two trees — a left-grouped tree and a right-grouped tree are structurally different parse trees for the same string. That is exactly the definition of ambiguity, so G₁ is ambiguous.

Now apply the same test to G₂: S → aB / ab, A → AB / a, B → Abb / b. Splitting the recursion across three non-terminals can look 'safer' at a glance than G₁'s single self-recursive rule, but the definition still has to be checked directly rather than assumed. Look at the two S-productions themselves: S → aB and S → ab both start by consuming the terminal 'a', and B can itself derive 'b' directly.

Parse tree

Derivation

String

Tree A

S ⇒ ab (single production)

ab

Tree B

S ⇒ aB ⇒ ab (using B → b)

ab

Tree A expands S directly into the two terminals 'a' and 'b' in one step. Tree B expands S into 'a' followed by the non-terminal B, which then expands into 'b' — an extra internal node that Tree A does not have. The two trees are structurally different, yet both derive the identical string 'ab'. By the same definition used for G₁, that makes G₂ ambiguous as well.

This second case is easy to miss because it does not come from deep recursion — it comes from the start symbol having two competing productions (aB and ab) that overlap on a short string once B is allowed to derive 'b' directly. Checking that overlap, rather than assuming a grammar spread across several non-terminals is automatically unambiguous, is exactly the step a check based only on G₁'s recursive shape would skip.

Since both G₁ and G₂ independently satisfy the definition of an ambiguous grammar — each has at least one generated string with two distinct parse trees — the correct option is that both G₁ and G₂ are ambiguous.

Explore the full course: Nta Ugc Net Paper 2

Loading lesson…