Which of the following grammars is(are) ambiguous? (A) \(s \rightarrow ss \mid…
2020
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)
Attempted by 78 students.
Show answer & explanation
Correct answer: D
(A) S→SS∣aSb∣bSa∣λ
✔ Ambiguous — EASY reason
Because of S → SS, strings can be divided in multiple ways.
Example:
String "ab"
Derivation 1:
S⇒aSb⇒abS
Derivation 2:
S⇒SS⇒aS bS⇒abS
Two different parse trees → ambiguous.
✔ Confirmed ambiguous
(B) S→asbs∣bsas∣λS
Because SSS can appear inside itself, and the outer pattern can be matched in multiple ways.
Example string:
Take string: "asbsasbs"
We can parse it in two different ways:
Parse 1
Treat whole string as:
S⇒asbSS
Inner S = "sbs"
Then:
S⇒asb(asbS)⇒...
Parse 2
Break string earlier:
S⇒asbS⇒asb(asbS)S
OR
S⇒asbS⇒asb(λ)S
and outer S wraps differently.
Because boundaries of S → asbs can be chosen in multiple ways, the SAME FINAL STRING gets TWO DIFFERENT parse trees.
✔ Grammar (B) is ambiguous
(C)
S→aABS
A→bBbA
B→A∣λB
✔ Ambiguous because of indirect recursion between A and B
Notice:
B→AB
A→bBbA
So A and B refer to each other — this allows multiple choices for B.
Example string:
Generate:
S→aABS
Option 1:
B→λB
Then
A → b B b → b λ b = bb
So string = "a bb"
Option 2:
B→AB
Then A → b B b
B → λ
Now A = b (λ) b = bb
And B = A = bb
Final string = a A B = a bb bb = abb bb
But also, we can choose A’s B to become A again and create different nesting structures, but the same final string length may occur with different parse tree structures.
Because B → A allows multiple recursive derivation paths that ultimately collapse to same number of b’s, the same string can be generated in multiple ways.
✔ So grammar (C) also ambiguous
Final Answer
All three grammars — (A), (B), and (C) — are ambiguous.
A video solution is available for this question — log in and enroll to watch it.