Skip to main content

CNF: S→XYZ|XY|aZ

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.

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}

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:

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.
S → XY | Y
X → abX | ab
Y → bY | ab

Step 3: Remove unit production S → Y

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).

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)bab, with strings like ab, abab, bab, ababbab.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →