Consider the following grammar: S → ASB | ϵ A → aAS | a B → SbS | A | bb (i) Eliminate ϵ-productions; (ii) Eliminate any unit productions in the resulting grammar; (iii) Eliminate any useless symbols in the resulting grammar; (iv) Put the resulting grammar into Chomsky Normal Form (CNF)?

(i) Only S is null able, so we must chose, at each point where S occurs in a body, to eliminate it or not. Since there is no body that consists only of S’s we do not have to invoke the rule about not eliminating an entire body.

The resulting grammar:

S → ASB | AB

A → aAS | a | aA

B → SbS | A | bb | bS | Sb | b

(ii) The only unit production is B → A. Thus, it suffices to replace this body A by the bodies of all the A-productions:

The result:

S → ASB | AB

A → aAS | a | aA

B → SbS | aAS | a | aA | bb | bS | Sb | b

(iii) Observe that A and B each derive terminal strings and therefore so does S. Thus, there are no useless symbols.

(iv) Introduce variable and productions C → a and D → b, and use the new variables in all bodies that are not a single terminal:

S → ASB | AB

A → CAS | a | CA

B → SDS | CAS | a | CA | DD | DS | SD | b

C → a

D → b

Finally, there are bodies of length 3; One, CAS appears twice. Introduce new variables E, F and G to split these bodies, yielding the CNF grammar:

S → AE | AB

A → CF | a | CA

B → SG | FC | a | CA | DD | DS | SD | b

C → a

D → b

E → SB

F → AS

G → DS