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:

- Eliminating ϵ-productions
- Eliminating unit productions
- Restricting the right side of the production to single terminals or strings of two or more variables
- 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-> SX_{1}

S -> X_{6}

X_{1} -> X_{2}X_{3}

X_{2} -> (

X_{4} -> SX_{5}

X_{5} -> )

S -> X_{2}X_{4}/ SX_{6}

X_{6} -> X_{2}X_{5}

**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.