Skip to main content

CNF conversion (grammar with S→A|B)

Short answer

After removing unit productions, the CNF is: S → XaP | XaQ | a | b | XaXb | ε, A → XaP, B → XaQ | a | b | XaXb, with P → BXa, Q → AXb, Xa → a, Xb → b.

Convert the following CFG to CNF. [Heading and grammar are cut off in the scan. The worked solution starts from S → A | B | ε, A → aBa, B → aAb | a | b | ab (after removing null productions), so the original grammar had ε-productions for A and B.]

Grammar. The heading is cut off in the question. From the given null-free form we take the grammar

S → A | B | ε; A → aBa; B → aAb | a | b | ab

(this is the original S → A | B, A → aBa | ε, B → aAb | a | b after removing ε-productions). We convert it to CNF.

Step 1: Start symbol

S does not occur on a right side, so S → ε can stay.

Step 2: ε-productions

Already removed except S → ε (allowed for the start symbol).

Step 3: Remove unit productions S → A and S → B

S → aBa | aAb | a | b | ab | ε
A → aBa
B → aAb | a | b | ab

Step 4: Convert to CNF

Terminals: Xa → a, Xb → b. Long rules: aBa = Xa P with P → B Xa; aAb = Xa Q with Q → A Xb; ab = Xa Xb.

S  → XaP | XaQ | a | b | XaXb | ε
A  → XaP
B  → XaQ | a | b | XaXb
P  → BXa
Q  → AXb
Xa → a
Xb → b

Every production has the form X → YZ or X → a (and S → ε for the start). This is the CNF.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →