Let G be a context-free grammar where G = ({S, A, B, C}, {a, b, d}, P, S) with the productions P given below (epsilon denotes the null/empty string): S -> AbB | c A -> aAb | epsilon B -> Ad | b C -> epsilon Transform the grammar G to an equivalent context-free grammar G' that has no epsilon-productions and no unit productions. (A unit production is of the form X -> Y where X and Y are non-terminals.)

GATE 1996 · Compiler Design · Grammar · medium

Answer: G' = ({S, A, B}, {a, b, c, d}, P', S) with productions: S -> AbB | bB | c; A -> aAb | ab; B -> Ad | d | b. This grammar is equivalent to G with no epsilon-productions and no unit productions.

1. Find nullable non-terminals: A -> epsilon => A is nullable. C -> epsilon => C is nullable. B -> Ad: A is nullable, so if A is removed we get B -> d (not epsilon). B -> b (terminal, not epsilon). So B is NOT nullable. S -> AbB: even if A is removed, bB remains; not epsilon. S -> c (terminal). S is NOT nullable. So Nullable = {A, C}. Note: C does not appear in any other production, so it has no effect on other rules.
2. Eliminate epsilon-productions: For A -> aAb: A appears on the right and A is nullable. Add: A -> aAb (keep A), A -> ab (remove A). Drop A -> epsilon. For S -> AbB: A is nullable. Add: S -> AbB (keep A), S -> bB (remove A). B is not nullable so no further variants. For B -> Ad: A is nullable. Add: B -> Ad (keep A), B -> d (remove A). For B -> b: no nullables, keep as is. S -> c: keep as is. New productions after epsilon-elimination: S -> AbB | bB | c A -> aAb | ab B -> Ad | d | b
3. Check for and eliminate unit productions: After step 2, the productions are: S -> AbB | bB | c A -> aAb | ab B -> Ad | d | b Check each production right-hand side: - S -> AbB: right side has two symbols (A and bB), not a single non-terminal. Not a unit production. - S -> bB: 'b' is a terminal followed by B, not a single non-terminal. Not a unit production. - S -> c: 'c' is a terminal. Not a unit production. - A -> aAb: not a unit production. - A -> ab: not a unit production. - B -> Ad: not a unit production. - B -> d: 'd' is a terminal. Not a unit production. - B -> b: 'b' is a terminal. Not a unit production. There are no unit productions in the grammar after step 2. The grammar is already free of unit productions.
4. Final equivalent grammar G': G' = ({S, A, B}, {a, b, c, d}, P', S) where P' is: S -> AbB | bB | c A -> aAb | ab B -> Ad | d | b This grammar has no epsilon-productions and no unit productions and generates L(G).