---
title: "CNF: S→AB, A→aAA|ε, B→bBB|ε"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-conversion-ab-epsilon"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-conversion-ab-epsilon
site: BCT Engineering
---

# CNF: S→AB, A→aAA|ε, B→bBB|ε

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Chaitra
- Video: [Chomsky Normal Form || Converting CFG to CNF || TOC || FLAT || Theory of Computation](https://www.youtube.com/watch?v=zTNm1nzDKUg) — Sudhakar Atchala
- 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-ab-epsilon
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Convert the given context free grammar (CFG) into an equivalent CNF: S → AB; A → aAA | ε; B → bBB | ε (ε is the empty symbol).

## Short answer

Remove ε-productions: S→AB|A|B|ε, A→aAA|aA|a, B→bBB|bB|b. Remove unit productions: S→AB|aAA|aA|a|bBB|bB|b|ε. Introduce Xa→a, Xb→b, C→AA, D→BB. CNF: S→AB|XaC|XaA|a|XbD|XbB|b|ε, A→XaC|XaA|a, B→XbD|XbB|b, C→AA, D→BB, Xa→a, Xb→b.

## Answer

**Grammar:** S → AB; A → aAA | ε; B → bBB | ε.

#### Step 1: Start symbol
S does not appear on any right-hand side, so no new start symbol is needed.

#### Step 2: Remove ε-productions
Nullable: A, B, and S (S → AB). Generate all variants:
- S → AB gives AB | A | B (we drop the all-ε variant; ε stays only for S).
- A → aAA gives aAA | aA | a.
- B → bBB gives bBB | bB | b.

```text
S → AB | A | B | ε
A → aAA | aA | a
B → bBB | bB | b
```

S → ε remains because ε ∈ L(G) and S is the start symbol not occurring on a right side.

#### Step 3: Remove unit productions
S → A and S → B are units. Replace by the rules of A and B:

```text
S → AB | aAA | aA | a | bBB | bB | b | ε
A → aAA | aA | a
B → bBB | bB | b
```

#### Step 4: Convert to CNF
Terminals inside longer rules: Xa → a, Xb → b. Break long rules: C → AA, D → BB.

```text
S  → AB | XaC | XaA | a | XbD | XbB | b | ε
A  → XaC | XaA | a
B  → XbD | XbB | b
C  → AA
D  → BB
Xa → a
Xb → b
```

All rules have the form X → YZ or X → a (S → ε allowed for the start). This is the required CNF.

## Check yourself

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

1. Why is no new start symbol needed here?
   A. S is nullable
   B. S does not appear on any right-hand side
   C. S has a unit production
   D. The grammar has no terminals
   Answer: B. A new start is needed only if S occurs on a right side; here it does not. (Key point: Why no new start)

2. Removing ε-productions, A → aAA gives which rules?
   A. aAA only
   B. aAA | aA | a
   C. aAA | AA
   D. aAA | aA | a | ε
   Answer: B. Each A may be dropped: aAA, aA (one A deleted) and a (both deleted). (Key point: Removing ε from A → aAA)

3. What do you do with the unit productions S → A and S → B?
   A. Delete them with no replacement
   B. Replace them with the right sides of A and B
   C. Convert them to terminals
   D. Keep them since CNF allows them
   Answer: B. Unit rules are replaced by the non-unit productions of the variable they point to. (Key point: Unit productions)

4. Which new rules shorten aAA and bBB in CNF?
   A. C → aA, D → bB
   B. C → Xa A, D → Xb B
   C. C → AA, D → BB
   D. C → a, D → b
   Answer: C. After replacing terminals with Xa, Xb, the rules XaAA and XbBB become XaC and XbD with C → AA and D → BB. (Key point: Splitting long rules)

## 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 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
- [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×
- [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
- [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

## Related in other subjects

- [Context-sensitive, context-free, regular grammars](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-types-context-sensitive-free-regular) — Discrete Structure, chapter 2
- [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×
- [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2×