Chomsky Normal Form(CNF)
In this class, We discuss Chomsky Normal Form(CNF).
For Complete YouTube Video: Click Here
The reader should have prior knowledge of eliminating epsilon, unit, and useless productions. Click Here.
Chomsky Normal Form: A context-free grammar is said to be in Chomsky normal form if productions are of the form
A – BC
A – a
The right side of the production should Contain two nonterminals or a single terminal.
If the CFG is not in the CNF, we need to convert the CFG into CNF.
Take an example and understand the conversion process.
Example 1:
S – aAD
A – aB | bAB
B – b
D – d
First step:
Eliminate epsilon, unit, and useless productions.
The grammar above does not have the unit, epsilon, or useless productions.
Second Step:
Give terminals a separate production.
In the above example, the terminals b, d are in CNF.
So we assign a new production to terminal a.
C1 – a
C2 – b
Now we substitute and convert.
S – C1AD
A – C1B | C2AB
B – b
D – d
The production S is not in CNF, and we add one more nonterminal D1 and convert it to CNF.
S – C1D1
D1 – AD
The above two productions are in CNF.
Similarly, we do for all the remaining productions.
The below grammar shows the CFG after converting to CNF.
S – C1D1
D1 – AD
A – C1B | C2D2
D2 – AB
B – b
D – d
C1 – a
C2 – b
Example 2:
S – abAB
A – bAB | ε
B – BAa | ε
First, we need to eliminate epsilon.
The below grammar shows the CFG after eliminating epsilon productions.
S – abAB | abA | abB | ab
A – bAB | bB | bA | b
B – BAa | Ba | Aa | a
Now, we take extra productions to terminals.
C1 – a
C2 – b
Substitute and convert
S – C1C2AB | C1C2A | C1C2B | C1C2
A – C2AB | C2B | C2A | b
B – BAC1 | BC1 | AC1 | a
We convert each production into CNF
Take the production S – C1C2AB. We have four nonterminals.
So we take two extra nonterminals and covert as
S – DE
D – C1C2
E – AB
The above conversion is in CNF.
Similarly, do the remaining.
The below shown CFG is in CNF.
S – DA
S – DB
S – C1C2
A – C2E | C2B | C2A | b
B – FC1 | BC1 | AC1 | a
F – BA