Chomsky Normal Form (CNF)

 

📘 Chomsky Normal Form (CNF)

✅ Definition

A context-free grammar (CFG) is said to be in Chomsky Normal Form if every production rule is of the form:

1. Two nonterminals:

   $$A \;\to\; BC$$
   

   where $A, B, C$are variables (nonterminals) and neither $B$ nor $C$ is the start symbol.

2. Single terminal:

   $$A \;\to\; a$$
   

   where $a$ is a terminal symbol.

3. Optional ε-production (only if the language includes ε):

   $$S \;\to\; \varepsilon$$
   

   allowed only if $S$ is the start symbol and $S$ does not appear on the right-hand side of any rule.

---

❌ What is NOT allowed

• Rules like $A\to \epsilon$ (except possibly for start symbol).

• Rules like $A\to B$ (unit productions).

• Rules like $A\to aB$ (mix of terminal + nonterminal).

• Rules with more than 2 nonterminals on the RHS (e.g., $A\to BCD$).

• Rules with more than 1 terminal on the RHS (e.g., $A\to ab$).

---

🌟 Example 1: Grammar in CNF

A→AB∣BC

A→BA∣a

B→CC∣b

C→AB∣a

✔ All productions are either of type $A\to BC$ or $A\to a$
So this grammar is in CNF.

---

🚫 Example 2: Grammar NOT in CNF

    S→AAS

    A→aa

• $S\to AAS$❌ not allowed (3 symbols on RHS).

• $A\to aa$ ❌ not allowed (2 terminals together).

---

🛠 Why CNF is Special

1. Simplifies parsing algorithms (like CYK algorithm).

2. Provides a canonical form → easier to prove properties of CFGs.

3. Ensures maximum standardization: every CFG can be converted into an equivalent CNF (except for ε-productions).

📘 Theorem (CNF Conversion)

Theorem:
Any context-free grammar $G=(V,T,S,P)$ with $\lambda \mathrm{\notin }L(G)$ has an equivalent grammar in Chomsky Normal Form (CNF).

---

✨ Proof 

We want to systematically rewrite $G$ into an equivalent grammar $G^{\mathrm{\prime }}$in CNF.

🔹 Step 0: Simplification

any CFG can be converted to one without:

• λ-productions (except possibly $S\to \lambda$)

• unit-productions

• useless symbols

So we assume $G$ is already simplified.

---

🔹 Step 1: Remove terminals from long productions

Every production has the form:

$$A\to x_1{x}_2\cdots x_n,n\ge 1$$

where each $x_i\in V\cup T$

• If $n=1$, then $x_1$ must be a terminal $a$. Keep $A\to a$
  

• If $n\ge 2$:

  • For each terminal $a\in T$, introduce a new variable $B_a$

  • Replace $a$ in the rule with $B_a$

  • Add the rule $B_a\to a$

✅ At the end, every production looks like:

• $A \to C_1 C_2 \cdots C_n$, where each $C_i\in V_1$(no terminals mixed in).

• Or $A\to a$

---

🔹 Step 2: Break down long right-hand sides

Now, if we still have rules like $A\to C_1{C}_2{C}_3\cdots C_{\mathrm{n }}$with $n\ge 3$:

Introduce new variables $D_1, D_2, \dots$to "chain" the production into binary form:

$$A\to C_1{D}_1,D_1\to C_2{D}_2,\dots ,D_{n-2}\to C_{n-1}{C}_n$$

✅ At the end, every production is either:

• $A\to BC$ (two variables), or

• $A\to a$ (a single terminal).

Thus, the grammar is in CNF.

Example:

S → A B a

A → a a b

B → A c

1) Identify terminals and nonterminals

Nonterminals: S, A, B
Terminals: a, b, c

No ε-productions or unit-productions are present, so we can proceed.

2) Replace terminals that occur in productions of length ≥ 2

Introduce new nonterminals that produce single terminals:

X_a → a
X_b → b
X_c → c

Replace occurrences of terminals in RHS of length > 1:

• S → A B a ⇒ S → A B X_a

• A → a a b ⇒ A → X_a X_a X_b

• B → A c ⇒ B → A X_c

Now every RHS contains only nonterminals, but some RHSs are length 3.

3) Binarize RHSs of length > 2

Replace length-3 RHSs with chains of binary productions by introducing new helper nonterminals.

For A → X_a X_a X_b introduce D1:

A → X_a D1
D1 → X_a X_b

For S → A B X_a introduce D2:

S → A D2
D2 → B X_a

B → A X_c is already binary (A and X_c), so keep it.

4) Final grammar in CNF

Nonterminals: S, A, B, D1, D2, X_a, X_b, X_c
Terminals: a, b, c

Productions (all in CNF form A → BC or A → a):

S  → A D2
D2 → B X_a

A  → X_a D1
D1 → X_a X_b

B  → A X_c

X_a → a
X_b → b
X_c → c

Each production is either two nonterminals on the right (A → BC) or a single terminal (X_a → a, etc.), so the grammar is in CNF. This grammar generates the same language as the original one (no λ in the original language), so the conversion is correct.