Theory of Computation – Chomsky Normal Form

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-> SX₁
S -> X₆
X₁ -> X₂X₃
X₂ -> (
X₄ -> SX₅
X₅ -> )
S -> X₂X₄/ SX₆
X₆ -> X₂X₅

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.