L8 Chomsky Normal Form

Chomsky Normal Form
Definition Chomsky Normal Form (CNF)
A grammar is in Chomsky Normal Form (CNF), if it has only productions of the form:
A ? B C or
A ? a
with A, B, C ?V and a?T.
This means all rules are consisting of either a single terminal on the production, or they are binary, consisting of two variables.
Conversion of a CFG into Chomsky Normal Form
Here is the algorithm to convert a given CFG into CNF.
1. Make the initial grammar G free of ?-productions, unit-productions, and useless variables and productions.You have rules now, which contain one terminal on the productions or at least two symbols from V ? T on the productions.
2. We substitute terminals ai, which appear in complex PRODUCTIONS (with more than one symbol), with new variables C1, C2,...
Add these C1, C2,... to V to form V .
We have to add matching new productions: Ci ? ai to P to form P .
Productions in P have either a single terminal on the productions, or at least 2 variables:
A ? a or A ? V1 ... Vn with Vi ? V for i=1,...,n and n?2
3. We split up the non-terminal productions in P and make them "binary".
We introduce new variables D1, D2, ... which we add to V .
Every A ? V1 ... Vn in P is now substituted with a set of new productions:
A ? V1 D1
D1 ? V2 D2
D2 ? V3 D3
. . .
Dn-1 ? Vn-1 Vn
The grammar is now in Chomsky NF:

Example 1: Transform a CFG into Chomsky Normal Form the grammar G with V={S, A, B}, T={a, b} and productions P
S ? A
A ? a B a | a
B ? b A b | b |D

S ? a B a | a
B ? b A b | b

S ? C1 B C1 | a
B ? C2 A C2| b
C1?a
C2?b

S ? C1 D1 | a
B ? C2 D2 | b
D1? B C1
D2 ? A C2
C1? a
C2? b