What is the algorithm for Chomsky normal form?

Chomsky normal form (CNF) is a structured format for context-free grammar (CFGs). It enhances simplicity, making parsing and theoretical analysis more efficient. CNF production rules adhere to two specific patterns:

• One, where a non-terminal generates two other non-terminals

• Other, where a non-terminal generates a terminal symbol

This uniformity greatly simplifies parsing algorithms and eases the development of compilers by providing a consistent grammar structure conducive to formal language manipulation. Furthermore, CNF aids in resolving ambiguity within grammar and enables straightforward comparisons between different grammar systems, serving as an invaluable tool in formal language theory and compiler construction.

Algorithm

Suppose we have the given CFG as below.

The steps to convert a given CFG to Chomsky normal form are as follows:

Step 1: No start variable on the right side

In this step, we’ll ensure that the start symbol (usually denoted as $S$) is only used as the left-most symbol in production rules. This ensures a clear starting point for generating valid sentences, preventing structural ambiguities. The given CFG has a start symbol on the right in the second production rule. So we created a new start symbol, $S'$ as follows:

Step 2: Remove all null productions

Null productions are grammar rules where a non-terminal can generate an empty string $(ε)$. Eliminating these rules simplifies the grammar and eliminates potential confusion. We must find and replace rules that produce $ε$ with alternative productions to remove null productions. In our example, we have to remove null productions in rule 4, i.e., $Q$ $→$$λ$, so we can add $λ$ to the production$P$ $→$ $Q$$|$$S$, making it $P$ $→$ $Q$$|$$S$$|$$λ$ as follows:

Now, we’ll remove the null production $P$ $→$ $λ$ as told above.

Step 3: Remove all unit productions

Unit productions are grammar rules in which one non-terminal $P$ generates another non-terminal $Q$ directly. The recommended approach is to replace unit productions by directly incorporating non-terminal $Q$ productions where non-terminal $P$ is used. In our example, we’ll remove unit production $S→ S$.

Next, we’ll remove $S' →S$.

Next, we’ll remove $P→ Q$.

We’ll also remove $P→ S$ .

Step 4: Replace productions $P→ Q1...Qn$ where $n>2$

This step removes productions where a single non-terminal $P$ generates more than two symbols $(Q1...Qn)$ on the right side. This is accomplished by introducing new non-terminals and dividing the production into simpler components. For instance, we have$S ' → PSP$ ; we can replace it with $S' → PP'$ , where $P'→ SP$.

Step 5: Replace productions $P → pQ$ where $p$ is terminal, and $P$ and $Q$ are non-terminals

This step addresses productions where a terminal symbol $p$ is the initial symbol on the right side of a production. To handle this, we substitute such productions with a combination of new non-terminals and terminals as required. For instance, we have $S' → pQ$; we can replace it with $S' → Q'Q$, where $Q'→ x$.