The equivalent grammar corresponding to the grammar S → aA A → BB B → aBb | ε
2012
The equivalent grammar corresponding to the grammar
S → aA
A → BB
B → aBb | ε
- A.
S → aA
A → BB
B → aBb - B.
S → a | aA
A → BB
B → aBb | ab - C.
S → a | aA
A → BB | B
B → aBb - D.
S → a | aA
A → BB | B
B → aBb | ab
Attempted by 39 students.
Show answer & explanation
Correct answer: D
First, identify nullable non-terminals. B is nullable due to the production B → ε. Since A → BB, A becomes nullable if both B's derive empty strings. Eliminate epsilon productions. For B → aBb | ε, add the production B → ab where the inner B is removed. Update A to include single B: A → BB | B. Update S since A is nullable. Add the production S → a. The resulting grammar without epsilon productions preserves the original language.
A video solution is available for this question — log in and enroll to watch it.