Chomsky Normal Form Rules

Converting a grammar to CNF

When a grammar does not use lambda in any rule and has no unit productions, it is ready to convert to Chomsky normal form (CNF). CNF allows rules of only two types:

• $X\to c, \text{where }X\in V, \text{and }c\in \Sigma$
• $X\to YZ, \text{where }X,Y,Z \in V$

In other words, right-hand sides can only have a single (nonempty) terminal symbol or exactly two variables. If applicable, we can retain the empty string with the rule $S\to \lambda$, but only if $S$ does not appear on the right-hand side of any rule.

Sometimes we can remove ...