Chomsky Normal Form Rules

Learn how to convert a lambda and unit production free grammar to Chomsky normal form.

We'll cover the following

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:

  • Xc,where XV,and cΣX\to c, \text{where }X\in V, \text{and }c\in \Sigma
  • XYZ,where X,Y,ZVX\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λS\to \lambda, but only if SS does not appear on the right-hand side of any rule.

Sometimes we can remove SS from a replacement rule. Recall the grammar for anbn,SaSb    λa^nb^n, S\to aSb \;|\; \lambda. We can remove SS from the right-hand side as follows:

Get hands-on with 1200+ tech skills courses.