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-> 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.
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Buy Computer Science Books
- Buy Automata Theory Books
- Apply for Automata Theory Internship