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 | ε

  1. A.

    S → aA
    A → BB
    B → aBb

  2. B.

    S → a | aA
    A → BB
    B → aBb | ab

  3. C.

    S → a | aA
    A → BB | B
    B → aBb

  4. 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.

Explore the full course: Mppsc Assistant Professor