Question

Convert the following grammar G over Σ = {a, b} into Chomsky normal form. Note that G already satisfies the conditions on the start symbol S, λ-rules, useless symbols, and chain rules. Show your steps clearly.

S → bT

T → aAA | AbAT

A → aT | bT | a

Answer 1

## If all the production rules of given grammar G satisfies any one of the following rules, then the given grammar is in Chomsky Normal Form.

Rule 1 - A non terminal generating a terminal. (Example A --> a)
Rule 2 - A non terminal generating two non terminals ( Example T--> AA)
Rule 3 - ε (epsilon) generated by start symbol S.

Note = There can be more than one Chomsky normal form for a given grammar.

The grammar G given in above question is ,

S → bT

T → aAA | AbAT

A → aT | bT | a

# Following are the steps to convert above grammar to CNF ( Chomsky Normal Form) ,

Step 1
= We have to eliminate start symbol S from RHS. Since there is no start symbol S on RHS, this step is excecuted successfully.

Step 2
= We have to eliminate NULL, unit and useless productions. SInce there are no such productions this step is executed successfully.

Step 3
= We have to eliminate terminals from RHS if they exist with other terminals or non-terminals. So,

S --> BT
T --> CAA | ABAT
A --> CT | BT | C
B --> b (NEW PRODUCTION ADDED)
C --> a (NEW PRODUCTION ADDED)

Step 4
= RHS with more than two non-terminals are removed. So,
S--> BT
T --> CD | EF
D --> AA (NEW PRODUCTION ADDED)
E --> AB (NEW PRODUCTION ADDED)
F --> AT   (NEW PRODUCTION ADDED)
A --> CT | BT | C
B --> b
C --> a

In the above generated grammar we see the is unit production formation ( A --> C , C --> a)
Let us remove (as mentioned in step 2) as following,
S--> BT
T --> CD | EF
D --> AA
E --> AB
F --> AT
A --> CT | BT | a
B --> b
C --> a

The above grammar seems to follow all the 3 rules described at the starting of this solution to form a Chomsky Normal Form. Hence it is our final answer.

----------------------------------

# HENCE the CNF of given grammar G is following ,

S--> BT
T --> CD | EF
D --> AA
E --> AB
F --> AT
A --> CT | BT | a
B --> b
C --> a
----------------------------------