Compiler 강의노트 - Chomsky Normal form

Chomsky Normal form

For a Language grammar G, where G = (S, V, N, P),
Production Rules P are of the form as follow

A -> BC
A -> a

where A, B, C are nonterminal and a is terminal.

• It does not allow epsilon on the right side.
• Letf side can only has one non-terminal and right side has two non-terminal or single terminal.

---

Transform to Chomsky Normal form

1. Get rid of ε
2. Get rid of all productions RHS is one variable.
3. Replace long productions into shorter one.
4. Relpace all terminal of non single unit to non-terminal.

---

example

S -> ABa
A -> aab
B -> Ac

S -> AB(B_a)
A -> (B_a)(B_a)(B_b)
B -> A(B_c)

S -> AD
D -> B(B_a)
E -> (B_a)(B_b)
A -> (B_a)E
B -> A(B_c)