Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Chomsky Normal Form
3.
Example of Chomsky Normal Form
4.
Steps for Converting CFG to CNF
4.1.
Example
5.
Advantages of Chomsky normal form CNF
6.
Disadvantages of Chomsky Normal Form (CNF)
7.
Frequently Asked Questions
7.1.
What is Chomsky's normal form in TOC?
7.2.
What is Chomsky's theory called?
7.3.
What are the key elements of Chomsky's theory?
7.4.
What is the application of Chomsky's Normal Form?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Chomsky Normal Forms(CNF)

Author Malay Gain
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In the Theory of Computation, normalization is the process of standardizing the grammar rules of a certain language. It puts some restrictions on the grammar rules without changing the language. Normalization is performed using the different normal forms such as Chomsky Normal Form and Greibach Normal Form. Here we will be discussing the Chomsky Normal Form (CNF). 

chomsky normal form

Chomsky Normal Form

CFG (Context-Free Grammar) is a grammar model used to generate all possible patterns of strings in programming languages. CFG is a set of rules that defines the rules to from valid sentences and expressions in a particular language.
A Context-Free Grammar (CFG) is said to be in Chomsky Normal Form(CNF) if all of its grammar or production rules are of the form 

A → BC

or 

A → a

Where AB, and are non-terminal symbols and is a terminal symbol.

So, in  Chomsky Normal Form, we have restrictions on the length of RHS of the grammar rules i.e, RHS should be two non-terminal symbols otherwise a single terminal.

 

Next, we will see how to convert a given CFG to Chomsky Normal Form.

Also See, Moore Machine

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example of Chomsky Normal Form

In Chomsky Normal Form (CNF), the grammar is restricted to production rules having two non-terminals or a single terminal symbol on the right hand side. These rules can be expressed in the form

  • A non-terminal symbol generating two non-terminal symbols (A → BC)
  • A non-terminal symbol generating a terminal symbol (A → a)
  • A start symbol generating ε (S → ε)
     

Here A,B,C are non-terminal 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 non-terminal). Hence G2 is not Chomsky Normal Form.

Steps for Converting CFG to CNF

Follow the below steps for converting context-free 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 non-terminals, 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 → B|S,
         B → b|Ɛ
  }

 

Step 1: if we observe the production rules, we can find that in the first two rules starting state S appears right-hand 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 by 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 context-free 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 context-free grammar to Chomsky normal form can be computationally expensive, especially for grammars with complex structures or many non-terminal symbols.
  • Non-Intuitive 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 context-free grammar (CFG). The production rules of Chomsky Normal Form are limited to only single terminal and two non-terminal 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!

Previous article
Simplification of CFG(Context-Free Grammars)
Next article
Greibach Normal Form (GNF)
Live masterclass