Related Tags

# Chomsky's normal form

Ayesha Kanwal

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

### Overview

Chomsky's normal form (CNF) is a method to simplify context-free grammar.

Every grammar in CNF is context-free, and every CFGContext-free grammar. can be converted into CNF.

Grammar is in CNF if all the productions follow either of the following set of rules:

• Start symbol generates null.
• A nonterminal generates two nonterminals.
• A nonterminal generates one terminal.

### Steps to convert grammar to CNF

The following steps are used to convert context-free grammar into Chomsky's normal form.

1. Introduce a new start variable that produces the old start variable.
2. Remove the null productions from non-starting variables.
3. Remove the unit productions.
4. Convert all rules such that the right side has one terminal and two variables. New variables can be introduced to convert the rules.

### Example

Let's consider the following CFG:

#### Step 2: Remove null productions

Remove null productions iteratively. Replace the values of the variables that produce null in any other production.

### Result

The following grammar is in CNF.

Note: A single CFG can produce different Chomsky's normal forms.

RELATED TAGS

CONTRIBUTOR

Ayesha Kanwal