edited by
3,110 views
1 votes
1 votes

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

edited by

2 Answers

5 votes
5 votes

The solution is

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

A aA a

B bB b

C d

edited by
2 votes
2 votes

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.

Related questions