L8 Chomesky 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 .
Lec 8 : Computation Theory Chomsky Normal Form
2
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