---
title: "Define CNF; convert S→MaN|bL|bM grammar"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-define-convert-mln"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-define-convert-mln
site: BCT Engineering
---

# Define CNF; convert S→MaN|bL|bM grammar

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Shrawan
- Video: [Chomsky Normal Form & CFG to CNF Conversion](https://www.youtube.com/watch?v=Mh-UQVmAxnw) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-define-convert-mln
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

What is Chomsky Normal Form (CNF)? Convert the following grammar to CNF.
G = (S, L, M, N, a, b, c), Σ = {a, b, c}, R = {S → MaN | bL | bM; L → ab | cN | M | ε; M → a | cM; N → abN}

## Short answer

A CFG is in CNF if all productions are A → BC or A → a, with S → ε allowed if ε is in the language. The converted grammar is: S → XbL | b | XbM, L → XaXb | a | XcM, M → a | XcM, Xa → a, Xb → b, Xc → c.

## Answer

#### Chomsky Normal Form
A CFG is in **CNF** if every production has one of the forms

- A → BC (two variables), or
- A → a (one terminal),

and the start symbol may have S → ε if ε ∈ L (then S must not appear on any right side). Every CFG can be converted to CNF. CNF is used in the CYK parsing algorithm.

#### Conversion
**Grammar:** S → MaN | bL | bM; L → ab | cN | M | ε; M → a | cM; N → abN.

**Step 1: Useless symbols.** N → abN is the only rule for N and always contains N, so N generates no terminal string. Remove N and rules containing it:

```text
S → bL | bM
L → ab | M | ε       (cN removed)
M → a | cM
```

**Step 2: Remove ε.** Only L is nullable. S is not nullable, so no ε remains.

```text
S → bL | b | bM
L → ab | M
M → a | cM
```

**Step 3: Remove unit L → M.**

```text
S → bL | b | bM
L → ab | a | cM
M → a | cM
```

**Step 4: Convert to CNF.** Add Xa → a, Xb → b, Xc → c, replace terminals in long rules:

```text
S  → XbL | b | XbM
L  → XaXb | a | XcM
M  → a | XcM
Xa → a
Xb → b
Xc → c
```

This is in CNF. (Examples of strings generated: b, ba, bab, bca, bcca.)

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which pair of forms is allowed in Chomsky Normal Form?
   A. A → BC and A → a
   B. A → aB and A → a
   C. A → BCD and A → ε
   D. A → B and A → a
   Answer: A. CNF allows A → BC (two variables) or A → a (one terminal), plus S → ε for the start. (Key point: CNF definition)

2. Why is N removed in the conversion?
   A. N is nullable
   B. N is a unit variable
   C. N → abN always contains N, so N generates no terminal string
   D. N is the start symbol
   Answer: C. N has a single recursive rule without a base case, so it is non-generating. (Key point: Useless N)

3. After removing N, L → ab | M | ε: what does ε-removal do to S → bL?
   A. Leaves it unchanged
   B. Adds S → b alongside bL
   C. Removes S
   D. Adds S → ε
   Answer: B. Since L is nullable, S → bL gives bL and b; S is not nullable so no ε remains. (Key point: Nullable L)

4. Why are Xa, Xb, Xc introduced?
   A. To remove unit productions
   B. To remove ε-productions
   C. To make the grammar ambiguous
   D. To replace terminals in rules longer than one symbol
   Answer: D. Terminals in right sides with 2+ symbols are replaced by variables Xa → a, etc. (Key point: Terminal replacement)

## Related in Theory of Computation

- [CNF conversion (grammar with S→A|B)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-s-a-b) — Theory of Computation, chapter 3
- [CNF: S→AB, A→aAA|ε, B→bBB|ε](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-ab-epsilon) — Theory of Computation, chapter 3
- [CNF: S→XYZ|XY|aZ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-xyz) — Theory of Computation, chapter 3
- [CNF: S→ASB|ε, A→aAS|a, B→...](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-asb) — Theory of Computation, chapter 3
- [CNF: S→aAb|Ba|A, A→SS|ε, B→ε](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-aab-ba) — Theory of Computation, chapter 3

## Related in other subjects

- [Conversion to conjunctive normal form](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acnf-conversion-steps) — Artificial Intelligence, chapter 4, asked 3×
- [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2
- [NFA and DFA from grammar with A, B rules](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-with-a-b-productions) — Discrete Structure, chapter 2, asked 2×
- [Dynamic equation of GVF, wide rectangular form](https://www.bctengineer.com/question.md?key=semester_4%2Fhydraulics%3Agvf-dynamic-equation-wide-rectangular) — Hydraulics, chapter 8, asked 2×