Removing Unit productions

 

📌 What are Unit Productions?

A unit production is a production of the form:

$$A \to B$$

where A and B are variables (nonterminals).

👉 It does not introduce any terminal symbols or structure, it just "forwards" derivations from one variable to another.

Example:

A → B

C → D

These are unit productions.

They are considered redundant because instead of going through A → B → ..., we can directly substitute A with the right-hand side productions of B.

---

📌 How to Remove Unit Productions

We systematically replace them with equivalent non-unit productions:

Step 1: Identify all unit productions

• Find all rules of the form A → B.

Step 2: Compute unit pairs

A unit pair (A, B) means that $A \Rightarrow^* B$ using only unit productions.

• For each pair (A, B), we allow A to produce everything B produces (except ε, unless S is nullable).

Step 3: Replace unit productions

For every unit pair (A, B) and every non-unit rule B → α, add a rule A → α.

Step 4: Delete the original unit productions

Keep only the newly added useful rules.

---

📌 Example (your grammar after ε-removal)

We had:

S → A B a C | B a C | A a C | A B a | a C | B a | A a | a
A → B C | B | C
B → b
C → D
D → d

Step 1: Identify unit productions

• A → B

• A → C

• C → D

Step 2: Compute unit pairs

• (A, B)

• (A, C)

• (A, D) (because A → C and C → D)

• (C, D)

Step 3: Replace them

• From B → b, and (A, B) ⇒ add A → b.

• From C → D and D → d, and (A, D) ⇒ add A → d.

• From C → D and (A, C) ⇒ add all of D’s non-unit rules (D → d) ⇒ add A → d (already added).

• From (C, D) ⇒ add C → d.

Step 4: Remove unit productions

Final grammar without unit productions:

S → A B a C | B a C | A a C | A B a | a C | B a | A a | a

A → B C | b | d

B → b

C → D | d   (but C → D is still a unit rule → replace with C → d only)

D → d

After fully cleaning (removing last C → D):

S → A B a C | B a C | A a C | A B a | a C | B a | A a | a
A → B C | b | d
B → b
C → d
D → d

---

✅ Now we have a grammar with:

• No ε-productions

• No unit productions

Example

Given grammar

S → A a  |  B
B → A    |  b b
A → a    |  b c  |  B

1) Identify unit productions

Unit productions are of the form X → Y where both X and Y are variables:

• S → B

• B → A

• A → B

2) Compute unit-reachability (unit-closure)

Find which variables are reachable from which using only unit productions.

• From S: S → B and B → A, and A → B (loop), so S reaches {B, A} (and itself implicitly).

• From A: A → B and B → A ⇒ A reaches {B, A}.

• From B: B → A and A → B ⇒ B reaches {A, B}.

So the unit pairs (nontrivial) are:

• S → {A, B}

• A → {A, B}

• B → {A, B}

(We usually include the reflexive pair X→X, but what matters is that each variable can "inherit" non-unit productions from A and B.)

3) Collect all non-unit productions (RHS not a single variable)

These are the rules we will copy along unit edges:

• From A: A → a, A → b c

• From B: B → b b

• From S: S → A a is already non-unit (keep as is)

4) For each unit pair (X → Y) add X → α for every non-unit Y → α

• Since S reaches A and B, add to S the non-unit productions of A and B:

  • From A: add S → a, S → b c

  • From B: add S → b b

• Since A reaches A and B, add to A:

  • From B: add A → b b (it already has a and bc)

• Since B reaches A and B, add to B:

  • From A: add B → a, B → b c (and B already has b b)

5) Remove all original unit productions

Delete S → B, B → A, A → B.

6) Final grammar (no unit productions)

S → A a   |  a   |  b c   |  b b
A → a     |  b c |  b b
B → b b   |  a   |  b c

All productions now have either terminal(s) or a mixture (like A a) on the right-hand side — no rule of the form X → Y remains.