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 $S$ from a replacement rule. Recall the grammar for $a^nb^n, S\to aSb \;|\; \lambda$. We can remove $S$ from the right-hand side as follows: