Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

Chomsky's normal form

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

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 1: Add a new start state

Step 2: Remove null productions

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

Step 2.1: Removing BϵB \rightarrow \epsilon
Step 2.2: Removing AϵA \rightarrow \epsilon

Step 3: Remove unit productions

Step 3.1: Replace the productions produced by SS in S0S_0 and AA
Step 3.2: Replace the productions produced by BB in AA

Step 4: Incorporate one terminal and two variables in each production

Step 4.1: Introduce CaC \rightarrow a where aa occurs with a variable
Step 4.2: Introduce DASD \rightarrow AS where ASAS occurs with another variable

Result

The following grammar is in CNF.

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

RELATED TAGS

CONTRIBUTOR

Ayesha Kanwal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

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.

Keep Exploring