Conversion to Chomsky Normal Form

CNF, or Chomsky Normal Form, is a form in which the symbols that appear on the right of a production are strictly limited. The right side can contain either one terminal or two variables.

Below is a picture of the CNF conversion window:

Certain conventions are used in this program for creating new productions in the conversion to Chomsky Normal Form:

For terminals: B(a) -> a
Where a represents any terminal.
For expansion: D(#) -> AB
Where # is any integer and A and B are any two variables, including B(a) and D(#).
Integers used must start at 0, increase in increments of 1, and be numbered lower for rules near the top of the source grammar.

You must use B(a) and D(#).Using these new variables you can create new productions. The transformation of S->abAB is shown below.

NOTE: The rule S-> B(a)B(b)AB is not entered, but rather shown here as an intermediate step. This rule would be entered as the three rules shown below.

S->abAB

S->B(a)B(b)AB
B(a)->a
B(b)->b

S->B(a)D(2)
D(2)->B(b)D(1)
D(1)->AB

NOTE: Conversions that are already in CNF are placed in the grammar list box at the beginning.

Once you have transformed the grammar you can then check it to see if it is in correct CNF. If not you will be given an appropriate error message. If certain productions were not re-created from your CNF grammar then check your new productions carefully because it is easiest to make a mistake there. If you get stumped press the Show Answer button. Also, you can use the parser to see if your new grammar works in the language.