---
title: "CNF: S→aAb|Ba|A, A→SS|ε, B→ε"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-conversion-aab-ba"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-conversion-aab-ba
site: BCT Engineering
---

# CNF: S→aAb|Ba|A, A→SS|ε, B→ε

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2071 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-aab-ba
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Convert the following CFG to CNF.
G = (V, Σ, R, S), V = {S, A, B, a, b}, Σ = {a, b}, R = {S → aAb | Ba | A; A → SS | ε; B → ε}

## Short answer

After removing ε-productions and unit productions, the grammar becomes S0→aAb|ab|a|SS|ε, S→aAb|ab|a|SS, A→aAb|ab|a|SS. Introduce Xa→a, Xb→b, C→AXb. CNF: S0→XaC|XaXb|a|SS|ε, S→XaC|XaXb|a|SS, A→XaC|XaXb|a|SS, C→AXb, Xa→a, Xb→b.

## Answer

**Grammar:** S → aAb | Ba | A; A → SS | ε; B → ε.

#### Step 1: New start symbol
S appears on a right-hand side (A → SS), so add S0 → S.

#### Step 2: Remove ε-productions
Nullable variables: B (B → ε), A (A → ε) and S (S → A), so ε ∈ L(G).
- S → aAb gives aAb | ab.
- S → Ba gives Ba | a. B has no other rule (B generates only ε), so after removing B → ε the variable B generates nothing and the alternative Ba is dropped; only a remains.
- A → SS gives SS | S (one S deleted).
- Since ε ∈ L(G), keep S0 → ε (S0 is the start symbol and occurs on no right side).

```text
S0 → S | ε
S  → aAb | ab | a | A
A  → SS | S
```

#### Step 3: Remove unit productions
Units: S0 → S, S → A, A → S. Replace by the non-unit rules (S and A derive the same non-unit forms):

```text
S0 → aAb | ab | a | SS | ε
S  → aAb | ab | a | SS
A  → aAb | ab | a | SS
```

#### Step 4: Convert to CNF
Introduce Xa → a, Xb → b and C → AXb (for aAb = Xa A Xb):

```text
S0 → XaC | XaXb | a | SS | ε
S  → XaC | XaXb | a | SS
A  → XaC | XaXb | a | SS
C  → AXb
Xa → a
Xb → b
```

Every rule is of the form A → BC or A → a (and S0 → ε for the start symbol only). This is the CNF grammar. (Check: it generates ε, a, ab, aab, aabb, aa, ... same as the original.)

## Check yourself

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

1. Why is a new start symbol S0 → S added first?
   A. Because S appears on a right-hand side (A → SS)
   B. Because S is nullable
   C. Because S has unit productions
   D. Because S is a terminal
   Answer: A. When the start symbol occurs on a right side, a new start symbol that never appears on a right side is introduced. (Key point: New start symbol)

2. After removing B → ε, what happens to the production S → Ba?
   A. It becomes S → B
   B. It stays as Ba
   C. The variant a is kept and Ba is dropped, since B then generates nothing
   D. It becomes S → aa
   Answer: C. B generates only ε, so with B removed S → Ba gives only the variant S → a. (Key point: Dropping Ba)

3. Why is S0 → ε kept in the result?
   A. Because every CNF grammar needs an ε-rule
   B. Because A is nullable
   C. Because B is nullable
   D. Because ε ∈ L(G) and S0 appears on no right side
   Answer: D. S is nullable, so ε is in the language; CNF allows ε only from the start symbol. (Key point: Keeping S0 → ε)

4. Which rule shows how aAb is handled in CNF?
   A. S → aAb
   B. S → XaC with C → AXb
   C. S → XaXbA
   D. S → AXb
   Answer: B. Terminals become Xa, Xb and the three-symbol rule is split: aAb = Xa C where C → A Xb. (Key point: Final CNF 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
- [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
- [Ambiguity; language of S→SS|a](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aambiguity-inherent-ssa) — Theory of Computation, chapter 3