Notes

02/28/2014
Comp 285 – Theory of Computation
F 2/28/2014
Normal Forms
Chomsky Normal Form (use by CYK algorithm)
Greibach Normal Form (used in construction of npda acceptor)
Chomsky Normal Form
A CF Grammar is in Chomsky Normal Form iff all
produc(ons are in the form A → BC or A → a where
A,B,C are in V and a is in T.
Examples:
S → AS | a
yes!
A → SA | b
S → AS | AAS
no!
A → SA | aa
Converting a grammar to Chomsky Form (assuming no
λ-products and no unit productions)
S → ABa
Example: S → aSb | SS | ab
A → aab
B → Ac
Converting Any CF Grammar to Chomsky Normal Form
Clean the grammar by eliminating λ and unit productions
Construct a new grammar G1 = (V1,T,P1,S) as follows:
1. For all produc(ons A →x1x2…xn if n = 1 include A →x1 in P1. If
n > 1, for all a ε T introduce new variable Ba and add
production Ba → a to P1. Replace all terminals in A →x1x2…xn
with the corresponding A → C1C2…Cn and where Ci = xi if xi ε
V and Cj = Ba if xj = a. Add this production to P1.
2. Reduce all productions of the form A → C1C2…Cn for n > 2 and
Ci ε V by introducing new variables Di as follows: A → C1D1,
D1→ C2D2, D2 → C3D3 … Dn-2→ Cn-1Cn.
Greibach Normal Form
A CF Grammar is in Greibach Normal Form if all
produc(ons are in the form A → ax where a ε T and x ε V*
Note similarities and differences between s-grammar and Griebach Normal form
S → AB
Example: A → aA | bB | b is not GNF but easily converted!
B →b
Example: Convert S → abSb | aa to GNF
1

Download Report