---
title: "CNF conversion (grammar with S→A|B)"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-conversion-s-a-b"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-conversion-s-a-b
site: BCT Engineering
---

# CNF conversion (grammar with S→A|B)

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Chaitra
- Video: [Conversion of CFG to Chomsky Normal Form](https://www.youtube.com/watch?v=FNPSlnj3Vt0) — 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-conversion-s-a-b
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Convert the following CFG to CNF. [Heading and grammar are cut off in the scan. The worked solution starts from S → A | B | ε, A → aBa, B → aAb | a | b | ab (after removing null productions), so the original grammar had ε-productions for A and B.]

## Short answer

After removing unit productions, the CNF is: S → XaP | XaQ | a | b | XaXb | ε, A → XaP, B → XaQ | a | b | XaXb, with P → BXa, Q → AXb, Xa → a, Xb → b.

## Answer

**Grammar.** The heading is cut off in the question. From the given null-free form we take the grammar

S → A | B | ε; A → aBa; B → aAb | a | b | ab

(this is the original S → A | B, A → aBa | ε, B → aAb | a | b after removing ε-productions). We convert it to CNF.

#### Step 1: Start symbol
S does not occur on a right side, so S → ε can stay.

#### Step 2: ε-productions
Already removed except S → ε (allowed for the start symbol).

#### Step 3: Remove unit productions S → A and S → B

```text
S → aBa | aAb | a | b | ab | ε
A → aBa
B → aAb | a | b | ab
```

#### Step 4: Convert to CNF
Terminals: Xa → a, Xb → b. Long rules: aBa = Xa P with P → B Xa; aAb = Xa Q with Q → A Xb; ab = Xa Xb.

```text
S  → XaP | XaQ | a | b | XaXb | ε
A  → XaP
B  → XaQ | a | b | XaXb
P  → BXa
Q  → AXb
Xa → a
Xb → b
```

Every production has the form X → YZ or X → a (and S → ε for the start). This is the CNF.

## Check yourself

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

1. Why can S → ε stay in the CNF grammar?
   A. Because every start symbol can have ε
   B. Because S is also a terminal
   C. Because S does not occur on any right side
   D. Because A is nullable
   Answer: C. ε is permitted only for a start symbol that never appears on a right-hand side. (Key point: Start symbol rule)

2. Removing S → A and S → B gives which S rules?
   A. S → A | B
   B. S → aBa | aAb | a | b | ab | ε
   C. S → aBa only
   D. S → ab
   Answer: B. S takes over all non-unit rules of A and B. (Key point: Unit removal)

3. How is the rule aBa converted?
   A. Xa B Xa as one rule
   B. XaP with P → BXa
   C. aP with P → Ba
   D. PB with P → aa
   Answer: B. Replace terminals with Xa and split the three-symbol rule: Xa P where P → B Xa. (Key point: Splitting aBa)

4. How is B → ab written in CNF?
   A. B → ab
   B. B → Xa b
   C. B → XaXb
   D. B → a | b
   Answer: C. Both terminals are replaced by variables so the rule is two variables: XaXb. (Key point: Rule ab)

## Related in Theory of Computation

- [Define CNF; convert S→MaN|bL|bM grammar](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-define-convert-mln) — 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
- [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
- [CFG versus unrestricted grammar](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-vs-unrestricted-grammar) — Theory of Computation, chapter 4
- [Unrestricted grammar; superset of CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aunrestricted-grammar-explain) — Theory of Computation, chapter 4, asked 2×
- [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

## Related in other subjects

- [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
- [3-bus load flow with Q limits (cut off)](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Aload-flow-reference-load-generator-bus) — Power System Analysis II, chapter 2
- [Lateral load elements; stepwise [cut off]](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Alateral-elements-stepwise-74c) — Concrete Technology and Masonry Structure, chapter 9
- [Define scan conversion](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Awhat-is-scan-conversion) — Computer Graphics, chapter 2