Theory of Automata

Removal of Unit Production



Any Production Rule of the form A → B where A,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 grammar rule whenever B→x occurs in the grammar where [x belong to 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 and is the CFG which is containing the Unit Productions and G2 is the CFG which is derived from G1 after removal Unit Productions, Then

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

 Examples to 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 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 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 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 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 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

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest