Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 33

Chomsky Normal Form Conversion

Recommended resources

Hello! Welcome to your next lesson on the Theory of Computation.

In our previous lesson, we focused on "cleaning up" Context-Free Grammars by eliminating ε-productions and unit productions. We learned that these simplification steps are not only crucial for readability but are also a necessary prerequisite for more advanced transformations.

Today, we will build directly on that foundation. Our goal is to convert any Context-Free Grammar (CFG) into an equivalent grammar in Chomsky Normal Form (CNF). This is a highly standardized and restricted format for CFGs that has profound implications. By forcing every production rule into one of a few simple patterns, CNF makes grammars much easier to analyze and process algorithmically. This conversion is a cornerstone of many practical applications, including parsing algorithms (like CYK) used in compilers to check code syntax.

Let's begin by formally defining what Chomsky Normal Form is.

1. What is Chomsky Normal Form (CNF)?

A Context-Free Grammar is in Chomsky Normal Form if every one of its production rules adheres to one of the following three forms:

  1. A → BC: A variable produces exactly two other variables.
  2. A → a: A variable produces exactly one terminal symbol.
  3. S → ε: The start symbol S produces the empty string ε. (This rule is only allowed if the language contains ε, and if this rule exists, S cannot appear on the right-hand side of any rule).

Notice the strictness of these rules. There are no unit productions, no mixing of terminals and variables on the right-hand side, and no production bodies with more than two variables.

Lecture 9 - Parse Trees and Chomsky Normal Form

For a precise definition and a brief discussion on the benefits of CNF, please read the following excerpt from the 'Lecture 9 - Parse Trees and Chomsky Normal Form' notes.

Read the section titled '9.3 Chomsky Normal Form'. Pay close attention to Definition 9.1 and the commentary on how CNF simplifies the structure of parse trees into binary trees.

2. The Conversion Algorithm

So, how do we transform any given CFG into this restrictive form while ensuring it still generates the exact same language? We follow a systematic, multi-step algorithm. The process effectively combines the simplification techniques from our last lesson with a few new restructuring steps.

CFG Conversion Flowchart and Useless Symbol Removal
This flowchart illustrates the overall process. We begin with a CFG, perform simplifications (as we learned in the previous lesson), and then convert the simplified grammar to CNF.

The complete, ordered procedure is as follows:

  1. START: Add a new start symbol S_0 and a production S_0 → S. This isolates the start symbol, which is crucial if the original start symbol S appears on the right-hand side of a production. It also provides a clean way to handle the S → ε rule later if needed.
  2. DEL (Eliminate ε-productions): Remove all A → ε rules, as we learned in the previous lesson. If the language contains ε, the only ε-production remaining will be from the new start symbol, S_0 → ε.
  3. UNIT (Eliminate unit productions): Remove all A → B rules, again using the method from our last lesson.
  4. TERM (Handle terminals): Ensure terminals only appear alone in productions of the form A → a. For any rule where a terminal appears with other symbols (e.g., A → aB), create a new variable for that terminal (e.g., X_a → a) and substitute it into the original rule (making it A → X_a B).
  5. BIN (Binarize long rules): Break down any production with more than two variables on the right-hand side into a cascade of productions with exactly two variables. For example, A → BCD would become A → BZ_1 and Z_1 → CD.

This ordered process guarantees that each step's output is suitable for the next, leading to a valid CNF grammar.

3. A Step-by-Step Worked Example

Let's walk through the entire conversion process with a concrete example. The following video from Neso Academy provides an excellent demonstration. We will watch it in segments, corresponding to each step of our algorithm.

The grammar we'll convert is:

  • S → ASA | aB
  • A → B | S
  • B → b | ε

Step 1: Create a New Start Symbol

The original start symbol S appears on the right-hand side of the rule A → S. To conform to CNF rules, we must isolate the start symbol.

Conversion of CFG to Chomsky Normal Form

First, let's see how to add a new start symbol S'. (The video uses S' instead of our S₀).

Watch from 01:52 to 02:31. This clip shows the creation of the new start symbol and the rule S' → S.

Steps 2 & 3: Eliminate ε and Unit Productions

These are the simplification steps you're already familiar with. The video demonstrates how eliminating ε-productions can introduce new rules, and how subsequent elimination of unit productions further transforms the grammar.

Conversion of CFG to Chomsky Normal Form

Now, let's watch the simplification phase. This will be a good recap of our last lesson.

Watch from 02:31 to 09:12. This long segment covers the removal of both null and unit productions. Observe how the set of productions evolves as each simplification is applied.

Step 4 & 5: Restructure Productions (TERM and BIN)

This is where we apply the final transformations to meet the strict CNF format. After the previous steps, we have a grammar free of ε and unit productions, but it may still have rules that mix terminals with variables or have more than two variables on the right-hand side.

Converting CFG to Chomsky Normal Form (CNF) - Illustrated Steps
This image visually summarizes the final two steps: replacing terminals with new variables (e.g., `c` becomes `C`) and breaking long variable chains (e.g., `BCDE` is split using `D1`).

Now, let's watch the video complete the conversion.

Conversion of CFG to Chomsky Normal Form

The final part of the video handles these last two crucial steps: breaking down long rules (ASA) and isolating terminals from variables (aB).

Watch from 09:12 to the end (12:52). You will see how new variables are introduced to first binarize ASA and then to isolate the terminal a.

For another perspective, you can watch a second full example. Your background in building complex systems means you're likely comfortable with procedural algorithms, and seeing the process again will help solidify it.

A Chomsky Normal Form Example (Sipser 2.14 Solution)

This video from Easy Theory provides another complete walkthrough of the CNF conversion algorithm with a different example. It's a great way to reinforce the entire process from start to finish.

Watch the full video. Notice how the presenter verbalizes the five steps, which closely match the procedure we've outlined.

Test your understanding!

Let's apply the algorithm to a classic example: the language of palindromes over {a, b}. Convert the following grammar to CNF:

S → aSa | bSb | ε

Show answer

Here is the step-by-step conversion:

Original Grammar:

  • S → aSa | bSb | ε

Step 1: START
The language contains ε, so we'll need an ε-production from our new start symbol. Let's add a new start symbol S_0.

  • S_0 → S | ε
  • S → aSa | bSb | ε

Now, we perform the rest of the steps on the original grammar rules, aiming to generate L(G) - {ε}.

Step 2: DEL (Eliminate ε-productions)

  1. Nullable variables: S is nullable due to S → ε.
  2. New productions:
    • From S → aSa, substituting ε for S gives S → aa.
    • From S → bSb, substituting ε for S gives S → bb.
  3. New grammar (without S → ε):
    • S_0 → S | ε
    • S → aSa | bSb | aa | bb

Step 3: UNIT (Eliminate unit productions)
The only unit production is S_0 → S. We replace it by adding productions from S_0 to everything S can produce.

  • S_0 → aSa | bSb | aa | bb | ε
  • S → aSa | bSb | aa | bb

Step 4: TERM (Handle terminals)
The productions S_0 → aSa, S_0 → bSb, S → aSa, S → bSb mix terminals and variables. We introduce new variables for the terminals a and b.

  • Let A → a
  • Let B → b

Substitute these into the grammar:

  • S_0 → ASA | BSB | AA | BB | ε
  • S → ASA | BSB | AA | BB
  • A → a
  • B → b

Step 5: BIN (Binarize long rules)
The productions S_0 → ASA, S_0 → BSB, S → ASA, and S → BSB have three variables. We need to break them down.

  • Introduce a new variable C_1 → SA.
  • Introduce a new variable C_2 → SB.

Now, replace the long productions:

  • S_0 → AC_1 | BC_2 | AA | BB | ε
  • S → AC_1 | BC_2 | AA | BB
  • C_1 → SA
  • C_2 → SB
  • A → a
  • B → b

Every rule is now in a valid CNF format. This is the final grammar.

Conclusion

Today we have mastered a fundamental procedure in the theory of computation: converting any Context-Free Grammar into an equivalent one in Chomsky Normal Form. This process not only standardizes grammars but is a key enabling step for algorithms that decide properties of context-free languages.

Key Takeaways:

  • Chomsky Normal Form (CNF) restricts all productions to the forms A → BC, A → a, or S → ε.
  • This structured format simplifies parse trees into binary trees, which is computationally advantageous.
  • The conversion is a deterministic, multi-step algorithm that systematically cleans and restructures the grammar's rules.
  • The correct order of operations (START -> DEL -> UNIT -> TERM -> BIN) is crucial to ensure a correct and complete conversion.

Preview of the Next Lesson:
Now that we have CFGs in this powerful normal form, what can we do with them? In our next lesson, we will define regular grammars—a specific subclass of CFGs—and prove that they are precisely equivalent in power to the finite automata we studied earlier. This will forge a critical link between two major parts of our course: the world of regular languages and the world of context-free languages.