compiler design

Question

Let G be a context-free grammar where G = ({S, A, B, C}, {a, b, d}, P, S) with the productions in P given below.

S → ABAC

A → aA ∣ ε

B → bB ∣ ε

C → d

(ε denotes the null string). Transform the grammar G to an equivalent context-free grammar G′ that has no ε productions

and no unit productions. (A unit production is of the form x → y, and x and y are non terminals).

Answer 1

The solution is

S → ABAC /ABC/BAC/AAC/AC/BC/d

A → aA ∣ a

B → bB ∣ b

C → d

Comments

There is only one unit production $S\rightarrow C$ after removing null production from grammar, after removing $S\rightarrow C$,grammar will be -

S$\rightarrow$ ABAC/BAC/ABC/AAC/AC/BC/d

A$\rightarrow$aA/a

B$\rightarrow$bB/b

C$\rightarrow$d

---

yes ,thanks

---

Why not ABACd is not in the answer pls help where I am wrong..  :(

Answer 2

Answer given in gatebook  :  C->d is a unit production.

so first production will become S -> ABAd | BAd | AAd | ABd | Bd | d

A -> aA | a

B -> bB | b

A->aA/a ,B->bB/b comes from eliminating epsilon production,why we we remove C->d production(as the question says A unit production is of the form x → y, and x and y are non terminals).d is terminal i thing.

Comments

is d a non terminal?

---

how C->d is a unit production ?

unit productiona of type C->B

Plz correct me if i m wrong