---
title: "CNF: S→XYZ|XY|aZ"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cnf-conversion-xyz"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cnf-conversion-xyz
site: BCT Engineering
---

# CNF: S→XYZ|XY|aZ

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2070 Chaitra
- Video: [Converting CFG to CNF | Example | TOC | Lec-71 | Bhanu Priya](https://www.youtube.com/watch?v=7G0PwGrdlH8) — Education 4u
- 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-xyz
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Convert the CFG into CNF.
G = (V, Σ, R, S), V = {S, X, Y, Z, a, b, c}, Σ = {a, b, c}, R = {S → XYZ | XY | aZ; X → abX | ε; Y → bY | cZ | ab; Z → aXZ}

## Short answer

After removing useless symbols, ε-productions, and unit productions, the CNF is: S → XY | BY | AB, X → AP | AB, P → BX, Y → BY | AB, A → a, B → b.

## Answer

**Grammar:** S → XYZ | XY | aZ; X → abX | ε; Y → bY | cZ | ab; Z → aXZ.

#### Step 1: Remove useless symbols
Z → aXZ is the only rule for Z, and it always contains Z again. So Z can never derive a terminal string; Z is **non-generating**. Remove Z and every rule using it:

```text
S → XY          (XYZ and aZ removed)
X → abX | ε
Y → bY | ab     (cZ removed)
```

#### Step 2: Remove ε-productions
Only X is nullable.
- S → XY gives XY | Y.
- X → abX gives abX | ab.

```text
S → XY | Y
X → abX | ab
Y → bY | ab
```

#### Step 3: Remove unit production S → Y

```text
S → XY | bY | ab
X → abX | ab
Y → bY | ab
```

#### Step 4: Convert to CNF
Use A → a, B → b and P → BX (for abX = A P).

```text
S → XY | BY | AB
X → AP | AB
P → BX
Y → BY | AB
A → a
B → b
```

Every rule is A → BC or A → a. This is the CNF. (The language is (ab)*b*ab, with strings like ab, abab, bab, ababbab.)

## Check yourself

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

1. Why is Z removed as a useless symbol?
   A. Z is nullable
   B. Z → aXZ always contains Z again, so Z can never derive a terminal string
   C. Z is unreachable from S
   D. Z is the start symbol
   Answer: B. Z's only rule is recursive with no base case, so Z is non-generating. (Key point: Non-generating Z)

2. What happens to the rules containing Z, such as S → XYZ and S → aZ?
   A. They are kept
   B. They are changed to units
   C. They are removed, leaving S → XY
   D. They give S → X
   Answer: C. Any rule using a non-generating variable is deleted, leaving S → XY. (Key point: Effect of removing Z)

3. Why is useless-symbol removal done first here?
   A. It makes the grammar ambiguous
   B. It shrinks the grammar before the other steps, avoiding wasted work
   C. It is required by the CNF definition
   D. It removes all terminals
   Answer: B. Removing non-generating symbols early simplifies the later ε and unit removal. (Key point: Order of steps)

4. After ε-removal S → XY | Y, X → abX | ab, Y → bY | ab, how is S → Y eliminated?
   A. Replace it by S → bY | ab
   B. Replace it by S → X
   C. Delete without replacement
   D. Replace it by S → ε
   Answer: A. S → Y is replaced by the rules of Y, giving S → XY | bY | ab. (Key point: Unit removal)

## 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→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 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