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
H.W : Transform a CFG into Chomsky normal form (CNF)
S ?Y X Z \ Y
Y ?0Y1\01
X ?aXb\?
Z ?Bz
Greibach Normal Form
Definition Greibach Normal Form (GNF)
A CFG is in Greibach Normal Form if all productions are of the form
A ? a X
with a?T and X?V*.
This means, all productions start with a terminal on the PRODUCTION and have only variables following.
Theorem:
For every CFG G with ??L(G) exists an equivalent grammar G in Greibach NF.
Proof and algorithm
Firstly, we convert the given grammar into Chomsky NF:
Start with a grammar G = ( V, T, P, S)
Eliminate useless variables that cannot become terminals.
Eliminate useless variables that cannot be reached.
Eliminate ?-productions.
Eliminate unit productions.
Convert grammar to Chomsky Normal Form.
Then, we convert this grammar into an equivalent grammar in Greibach NF.