Skip to main content

CNF: S→aAb|Ba|A, A→SS|ε, B→ε

Short answer

After removing ε-productions and unit productions, the grammar becomes S0→aAb|ab|a|SS|ε, S→aAb|ab|a|SS, A→aAb|ab|a|SS. Introduce Xa→a, Xb→b, C→AXb. CNF: S0→XaC|XaXb|a|SS|ε, S→XaC|XaXb|a|SS, A→XaC|XaXb|a|SS, C→AXb, Xa→a, Xb→b.

Convert the following CFG to CNF. G = (V, Σ, R, S), V = {S, A, B, a, b}, Σ = {a, b}, R = {S → aAb | Ba | A; A → SS | ε; B → ε}

Grammar: S → aAb | Ba | A; A → SS | ε; B → ε.

Step 1: New start symbol

S appears on a right-hand side (A → SS), so add S0 → S.

Step 2: Remove ε-productions

Nullable variables: B (B → ε), A (A → ε) and S (S → A), so ε ∈ L(G).

  • S → aAb gives aAb | ab.
  • S → Ba gives Ba | a. B has no other rule (B generates only ε), so after removing B → ε the variable B generates nothing and the alternative Ba is dropped; only a remains.
  • A → SS gives SS | S (one S deleted).
  • Since ε ∈ L(G), keep S0 → ε (S0 is the start symbol and occurs on no right side).
S0 → S | ε
S  → aAb | ab | a | A
A  → SS | S

Step 3: Remove unit productions

Units: S0 → S, S → A, A → S. Replace by the non-unit rules (S and A derive the same non-unit forms):

S0 → aAb | ab | a | SS | ε
S  → aAb | ab | a | SS
A  → aAb | ab | a | SS

Step 4: Convert to CNF

Introduce Xa → a, Xb → b and C → AXb (for aAb = Xa A Xb):

S0 → XaC | XaXb | a | SS | ε
S  → XaC | XaXb | a | SS
A  → XaC | XaXb | a | SS
C  → AXb
Xa → a
Xb → b

Every rule is of the form A → BC or A → a (and S0 → ε for the start symbol only). This is the CNF grammar. (Check: it generates ε, a, ab, aab, aabb, aa, ... same as the original.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →