# Theory of Computation – Chomsky Normal Form

There are many normal forms for CFGs. They are the forms of context free grammar which are broad enough so that any grammar has an equivalent normal form version. You may think of it as cleaning up the grammar.

A context free grammar is in Chomsky normal form (CNF) if every production in the grammar is of any of form given below:
A -> BC
A -> a
Where A, B and C are variables and a is a terminal symbol.

Converting a context free grammar into Chomsky Normal Form can be done in four steps:

1. Eliminating ϵ-productions
2. Eliminating unit productions
3. Restricting the right side of the production to single terminals or strings of two or more variables
4. Finally reduce the long string of terminals at the right hand side to string of two terminals

Example: Convert the following grammar into Chomsky Normal Form
S -> S(S)/ ϵ
Solution:
The grammar after removal of null productions:
S -> S(S)/ (S)/ S()/ ()

There are no unit productions in the grammar

For converting into CNF we must make all the right hand side either containing 2 non-terminals or a terminal symbol. So converting the given grammar into CNF we get:
S-> SX1
S -> X6
X1 -> X2X3
X2 -> (
X4 -> SX5
X5 -> )
S -> X2X4/ SX6
X6 -> X2X5

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!