Chomsky Normal Form (CNF)
Definition: Let G = (N, T, P, S) be a CFG.
G is in Chomsky normal form if every rule in
P has one of these forms
• A ® BC, where A, B, C Î N;
• A ® a, where A Î N, a Î T;
Example:
G = (N, T, P, S), where N = {A, B, C, S}, T = {a, b},
P = {S ® CB, C ® AS, S ® AB, A ® a, B ® b}
is in Chomsky normal form.
Note: L(G)  = {anbn: n ³ 1}
2/10