Chomsky Normal Form (CNF)

It cannot contain the null, that CFG in which non-terminals belongs to two non-terminal. Or non-terminal belongs to only one terminal and non-terminal does not null, this is known as Chomsky Normal Form.

• Non-terminal = two non-terminal
• Non-terminal = only one terminal’
• Non-terminal ≠ Null

For Example:

S→aSb│bSb│aa│bb│a│b

It is not CNF. Now we will convert it into Normal Form by applying this method.

A→a

B→b

C→AS

D→BS

The CNF will be in this form:

S→ASA│BSB│AA│BB│A│B

S→ASA│BSB│AA│BB│a│b

S→CA│DB│AA│BB│a│b

Algorithm for Conversion into CNF:

Step 1:

If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’→ S.

Step 2:

Removal of the Null Production.

Step 3:

Removal of the unit production.

Step 4:

Replace each production A → B₁…B_n where n > 2 with A → B₁C. Where C → B₂ …B_n. Repeat this step for all productions having two or more symbols on the right side.

Step 5:

If the right side of any product is in the form A → aB. Where a is a terminal and A, B are non-terminal, then the production is replaced by A → XB and X → a. Repeat this step for every product which is in the form A → aB.

CFG Properties and Applications