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)/ ϵ
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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.