---
title: "CNF: S→ASB|ε, A→aAS|a, B→..."
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-conversion-asb"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-conversion-asb
site: BCT Engineering
---

# CNF: S→ASB|ε, A→aAS|a, B→...

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2074 Asoj
- 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-asb
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Convert the following CFG into CNF.
G = (V, Σ, R, S), V = {S, A, B, a, b}, Σ = {a, b}, R = {S → ASB | ε; A → aAS | a; B → AB | b | ε}

## Short answer

After removing ε-productions and unit productions, the CNF is: S0 → AC | AB | AS | XaD | XaA | a | ε, S → AC | AB | AS | XaD | XaA | a, A → XaD | XaA | a, B → AB | b | XaD | XaA | a, C → SB, D → AS, Xa → a.

## Answer

**Grammar:** S → ASB | ε; A → aAS | a; B → AB | b | ε.

#### Step 1: New start symbol
S occurs on a right side, so add S0 → S.

```text
S0 → S
S  → ASB | ε
A  → aAS | a
B  → AB | b | ε
```

#### Step 2: Remove ε-productions
Nullable: S and B (A is not nullable). Hence S0 is nullable.
- S → ASB gives ASB | AB | AS | A.
- A → aAS gives aAS | aA.
- B → AB gives AB | A.
- S0 → S, with S0 → ε kept.

```text
S0 → S | ε
S  → ASB | AB | AS | A
A  → aAS | aA | a
B  → AB | A | b
```

#### Step 3: Remove unit productions
Units: S0 → S, S → A, B → A. Replace:

```text
S0 → ASB | AB | AS | aAS | aA | a | ε
S  → ASB | AB | AS | aAS | aA | a
A  → aAS | aA | a
B  → AB | b | aAS | aA | a
```

#### Step 4: Convert to CNF
Introduce Xa → a, C → SB (for ASB = AC) and D → AS (for aAS = XaD).

```text
S0 → AC | AB | AS | XaD | XaA | a | ε
S  → AC | AB | AS | XaD | XaA | a
A  → XaD | XaA | a
B  → AB | b | XaD | XaA | a
C  → SB
D  → AS
Xa → a
```

All rules are now A → BC or A → a (S0 → ε only for the start symbol).

## Check yourself

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

1. Which variables are nullable in S → ASB | ε; A → aAS | a; B → AB | b | ε?
   A. A and B
   B. A only
   C. S and B
   D. S, A and B
   Answer: C. S → ε and B → ε make S and B nullable; A always produces a terminal. (Key point: Nullable variables)

2. Removing ε-productions, S → ASB yields:
   A. ASB | AB | AS | A
   B. ASB | SB
   C. ASB | AB | AS | A | ε
   D. ASB | A
   Answer: A. Delete S, B, or both: ASB, AB, AS, A (the all-ε case is not applicable since A stays). (Key point: ε-removal variants)

3. Which are the unit productions after ε-removal?
   A. A → a, B → b
   B. S → AS, B → AB
   C. None
   D. S0 → S, S → A, B → A
   Answer: D. A rule whose right side is a single variable is a unit production: S0 → S, S → A and B → A. (Key point: Unit productions)

4. How is ASB written in CNF?
   A. AC with C → SB
   B. XaD
   C. ASB stays
   D. SB with D → A
   Answer: A. A three-variable right side is split by introducing C → SB, so ASB = AC. (Key point: Splitting ASB)

## Related in Theory of Computation

- [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
- [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→XYZ|XY|aZ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-xyz) — 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→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

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