Skip to main content

CNF: S→ASB|ε, A→aAS|a, 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.

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 | ε}

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

Step 1: New start symbol

S occurs on a right side, so add S0 → S.

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

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →