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
It is not CNF. Now we will convert it into Normal Form by applying this method.
The CNF will be in this form:
Algorithm for Conversion into CNF:
If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’→ S.
Removal of the Null Production.
Removal of the unit production.
Replace each production A → B1…Bn where n > 2 with A → B1C. Where C → B2 …Bn. Repeat this step for all productions having two or more symbols on the right side.
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.