Normal Forms-
| Normalization is performed in order to standardize the grammar. |
- By reducing the grammar, the grammar gets minimized but does not gets standardized.
- This is because the RHS of productions have no specific format.
- In order to standardize the grammar, normalization is performed using normal forms.
Types of Normal Forms-
The most frequently used normal forms are-
- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)
In this article, we will discuss about Chomsky Normal Form.
Chomsky Normal Form-
|
A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form- A → BC or A → a where A, B, C are non-terminals and a is a terminal. |
From here, we infer-
- To be in CNF, all the productions must derive either two non-terminals or a single terminal.
- CNF restricts the number of symbols on the right side of a production to be two.
- The two symbols must be non-terminals or a single terminal.
Example-
S → AB
A → a
B → b
This context free grammar is in chomsky normal form.
Steps-
The following steps are followed to standardize the grammar using CNF-
Rule-01:
Reduce the grammar completely by-
- Eliminating ∈ productions
- Eliminating unit productions
- Eliminating useless productions
Also Watch- How To Reduce Grammar?
Rule-02:
Replace each production of the form A → B1B2B3….Bn where n > 2 with A → B1C where C → B2B3….Bn.
Repeat this step for all the productions having more than two variables on RHS.
Rule-03:
Replace each production of the form A → aB with A → XB and X → a.
Repeat this step for all the productions having the form A → aB.
PRACTICE PROBLEMS BASED ON CHOMSKY NORMAL FORM-
Problem-01:
Convert the given grammar to CNF-
S → aAD
A → aB / bAB
B → b
D → d
Solution-
Step-01:
The given grammar is already completely reduced.
Step-02:
The productions already in chomsky normal form are-
B → b ………..(1)
D → d ………..(2)
These productions will remain as they are.
The productions not in chomsky normal form are-
S → aAD ………..(3)
A → aB / bAB ………..(4)
We will convert these productions in chomsky normal form.
Step-03:
Replace the terminal symbols a and b by new variables Ca and Cb.
This is done by introducing the following two new productions in the grammar-
Ca → a ………..(5)
Cb → b ………..(6)
Now, the productions (3) and (4) modifies to-
S → CaAD ………..(7)
A → CaB / CbAB ………..(8)
Step-04:
Replace AD and AB by new variables CAD and CAB respectively.
This is done by introducing the following two new productions in the grammar-
CAD → AD ………..(9)
CAB → AB ………..(10)
Now, the productions (7) and (8) modifies to-
S → CaCAD ………..(11)
A → CaB / CbCAB ………..(12)
Step-05:
From (1), (2), (5), (6), (9), (10), (11) and (12), the resultant grammar is-
S → CaCAD
A → CaB / CbCAB
B → b
D → d
Ca → a
Cb → b
CAD → AD
CAB → AB
This grammar is in chomsky normal form.
Problem-02:
Convert the given grammar to CNF-
S → 1A / 0B
A → 1AA / 0S / 0
B → 0BB / 1S / 1
Solution-
Step-01:
The given grammar is already completely reduced.
Step-02:
The productions already in chomsky normal form are-
A → 0 ………..(1)
B → 1 ………..(2)
These productions will remain as they are.
The productions not in chomsky normal form are-
S → 1A / 0B ………..(3)
A → 1AA / 0S ………..(4)
B → 0BB / 1S ………..(5)
We will convert these productions in chomsky normal form.
Step-03:
Replace the terminal symbols 0 and 1 by new variables C and D.
This is done by introducing the following two new productions in the grammar-
C → 0 ………..(6)
D → 1 ………..(7)
Now, the productions (3), (4) and (5) modifies to-
S → DA / CB ………..(8)
A → DAA / CS ………..(9)
B → CBB / DS ………..(10)
Step-04:
Out of (8), (9) and (10), the productions already in Chomsky Normal Form are-
S → DA / CB ………..(11)
A → CS ………..(12)
B → DS ………..(13)
These productions will remain as they are.
The productions not in chomsky normal form are-
A → DAA ………..(14)
B → CBB ………..(15)
We will convert these productions in Chomsky Normal Form.
Step-05:
Replace AA and BB by new variables E and F respectively.
This is done by introducing the following two new productions in the grammar-
E → AA ………..(16)
F → BB ………..(17)
Now, the productions (14) and (15) modifies to-
A → DE ………..(18)
B → CF ………..(19)
Step-06:
From (1), (2), (6), (7), (11), (12), (13), (16), (17), (18) and (19), the resultant grammar is-
S → DA / CB
A → CS / DE / 0
B → DS / CF / 1
C → 0
D → 1
E → AA
F → BB
This grammar is in chomsky normal form.
To gain better understanding about Chomsky Normal Form,
Next Article- Algorithm To Decide Whether CFL Is Empty
Get more notes and other study material of Theory of Automata and Computation.
Watch video lectures by visiting our YouTube channel LearnVidFun.
