Introduction to Automata

Removal of Unit Production

Any Production Rule of the form A → B where A and B belong to Non-Terminals is called Unit Production. These Unit Production can be removed from CFG.

Procedure for Removal of Unit Production

Step 01: To remove A→ B, add production A→x to the grammar rule whenever B→x occurs in the grammar where [x belongs to the terminal, x can also be Null]

Step 2: Delete A→B from the grammar.

Step 3: Repeat from step 1 until all unit productions are removed.

Important: IF G1 is the CFG, which contains the Unit Productions, and G2 is the CFG, which is derived from G1 after the removal of Unit Productions, Then.

G1 must be equal to G2 (i.e. G1=G2)

 Examples of Remove Unit Productions

Example 01

Remove unit productions from a grammar (G1) whose production rule is given by

P: S→XY, X→a, Y →Z | b, Z→M, M→N, N→a                        // Grammar (G1)

In the above grammar (G1), Unit Productions are

  1. Y → | Z
  2. Z→ M
  3. M → N

The production unit, which is removed easily, is considered first. Let see,

For the Removal of Third Unit Production (M →  N)

As N→a So, Unit Production M → N is updated to M→a.

For the Removal of Second Unit Production (Z → M)

As we derived M→a in above case, So, Unit Production Z → M is updated to Z→a

For the Removal of First Unit Production (Y →  Z)

As we derived Z→a, So, Unit Production Y→Z is updated to Y→a

After Removal Unit Productions, the Updated Grammar (G2) is given below

P: S→XY, X→a, Y →a| b, Z→a, M→a, N→a            // Grammar (G2)

We can remove the unreachable states from the above grammar (G2). So Finally, Grammar (G2) is given below

P: S→XY, X→a, Y →a| b.                                         // Grammar (G2)

Note: Results of G1 and G2 will be similar.

Example 02

Remove unit productions from a grammar (G1) whose production rule is given by

P: S → aA | B, A → ba | bb, B → A | bba                       // Grammar (G1)

In the above grammar, Unit Production is

  1. S → B
  2. B→ A

The production unit, which is removed easily, is considered first. Let see,

For the Removal of 2nd Unit Production (B→ A)

As A→ba | bb. So, Unit Production B → A | bba is updated to B→ba | bb.

For the Removal of the first Unit Production (S →  B)

As B→A | ba | bb and A →ba|bb Therefore B→ ba | bb | bba. So,  Unit Production S → B is updated to S ba | bb | bba.

After Removal Unit Productions, the Updated Grammar (G2) is given below

P: S → aA | ba | bb | bba, A → ba | bb, B → A | bba                       // Grammar (G1)

We can remove the unreachable states from the above grammar (G2). So Finally, Grammar (G2) is given below

P: S → aA | ba | bb | bba, A → ba | bb                       // Grammar (G2)

Note: Results of G1 and G2 will be similar.

Unreachable states are those states which are not reachable from the initial state.