Example of Chomsky Normal Form
In Chomsky Normal Form (CNF), the grammar is restricted to production rules having two nonterminals or a single terminal symbol on the right hand side. These rules can be expressed in the form
 A nonterminal symbol generating two nonterminal symbols (A → BC)
 A nonterminal symbol generating a terminal symbol (A → a)

A start symbol generating ε (S → ε)
Here A,B,C are nonterminal symbols, a is a terminal symbol, S is the start symbol and ε denotes an empty string.
Let us understand Chomsky Normal Form with the help of an example.
Here we have two Grammar G1 and G2 which satisfy the rules for Context free grammar. Now we have to find if they specify the rules for Chomsky Normal Form.
G1 = { S → AB, S → c, A → a, B → b }
G2 = { S → aA, A → a, B → c }
Here we can see that G1 satisfies all the above rules for the Chomsky Normal Form. Hence the Grammar G1 is a Chomsky Normal Form. But for G2, it does not satisfy the above rules due to S → aA (terminal followed by a nonterminal). Hence G2 is not Chomsky Normal Form.
Steps for Converting CFG to CNF
Follow the below steps for converting contextfree grammar to Chomsky Normal Form.
Step 1: If the Start symbol S occurs on the right side of a grammar rule, create a new start symbol S’ and a new production or grammar rule S’ → S.
Step 2: Remove null production rules as well as unit production rules from the grammar.
Step 3: Replace each production rule A →B1B2……Bn where n>2, with A→B1C where C→B2…..Bn.
Repeat this step for all production rules of the CFG having two or more symbols on the right side.
Step 4: If the right side of any grammar rule is in the form A→aB where ‘a’ is a terminal symbol and A, B are nonterminals, then the production rule is replaced by A →XB and X →a.
Repeat this step for every production rule of the grammar which is of the form A→aB.
Let’s understand this concept through an example.
Example
Convert the given CFG to CNF:
G= { S → ASA  aB,
A → BS,
B → bƐ
}
Step 1: if we observe the production rules, we can find that in the first two rules starting state S appears righthand side of the productions. We need to add a new starting state S’ and a new production rule S’ → S.
Step 2: removing null production rules B →Ɛ and A →Ɛ.
After removing B →Ɛ, grammar G
S’ → S,
S → ASA  aB  a ,
A → B  S  Ɛ,
B → b
After removing A →Ɛ, grammar G
S’ → S,
S → ASA  aB  a  AS  SA ,
A → B  S ,
B → b
Removing unit production rules, S’ → S, A → B, and A →S
After removing S’ → S, grammar G
S’ → ASA  aB  a  AS  SA,
S → ASA  aB  a  AS  SA ,
A → B  S ,
B → b
After removing A → B, grammar G
S’ → ASA  aB  a  AS  SA,
S → ASA  aB  a  AS  SA ,
A → b  S ,
B → b
After removing A → S, grammar G
S’ → ASA  aB  a  AS  SA,
S → ASA  aB  a  AS  SA ,
A → b  ASA  aB  a  AS  SA ,
B → b
Step 3: we find some production rules that have more than two symbols on the RHS.
S’ → ASA, S → ASA, A → ASA .
Let’s replace SA by X i.e, X → SA
S’ → AX  aB  a  AS  SA,
S → AX  aB  a  AS  SA ,
A → b  AX  aB  a  AS  SA ,
B → b,
X → SA
Now we will replace terminal symbol a by Y from these rules, S’ → aB, S → aB and A → aB.
Now the grammar G in CNF
S’ → AX  YB  a  AS  SA,
S → AX  YB  a  AS  SA ,
A → b  AX  YB  a  AS  SA ,
B → b,
X → SA,
Y → a
Also, see Greibach Normal Form here
Advantages of Chomsky normal form CNF
Chomsky Normal Form (CNF) has many advantages in formal language theory and algorithm parsing. Some of these advantages include:

Simple and Standardized grammar

Efficient Parsing Algorithms

Less Grammar Size

Elimination of Empty String Rules
Also read  Arden's theorem
Disadvantages of Chomsky Normal Form (CNF)

Increased Size: Converting a contextfree grammar to Chomsky normal form can result in a significant increase in the number of production rules, leading to larger grammars.

Loss of Readability: The transformation process to CNF can make grammars less intuitive and harder to understand, especially for humans, due to the proliferation of intermediate variables.

Complexity of Transformation: Converting a contextfree grammar to Chomsky normal form can be computationally expensive, especially for grammars with complex structures or many nonterminal symbols.

NonIntuitive Representation: The resulting CNF may not reflect the original structure and semantics of the language, making it less intuitive to reason about the language's syntax and semantics.
Frequently Asked Questions
What is Chomsky's normal form in TOC?
In TOC Chomsky Normal Form is a special form of contextfree grammar (CFG). The production rules of Chomsky Normal Form are limited to only single terminal and two nonterminal symbols.
What is Chomsky's theory called?
Chomsky's theory, formed by Noam Chomsky is called Linguistic Theory or Chomskyan Generative Grammar.
What are the key elements of Chomsky's theory?
The key elements of Chomsky's theory include Universal grammar (noun, pronoun, adverb etc.), transformational rules between grammars, surface and deep structure language acquisition and most importantly a person's innate ability to learn grammar and language.
What is the application of Chomsky's Normal Form?
Chomsky's Normal Form is a type of context free grammar which is used to make the grammar more structured and easier to analyze. CNF is used in natural language processing, algorithm parsing, compiler design, grammar optimization etc.
Conclusion
This article covered concepts of Chomsky Normal Forms(CNF) and how CFG is converted to CNF.
We highly recommend you to visit the Coding Ninjas Studio library for getting a better hold of the computer fundamentals to crack your dream jobs.
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy learning!