Eliminating Unit Productions

In this class, We discuss Eliminating Unit Productions.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of eliminating epsilon productions. Click Here.

Eliminating epsilon productions will lead to unit productions.

First, we understand unit productions.

A – B, we call this unit production.

The left side is a single non-terminal and on the right side single non-terminal.

Example 1:

S – AB

A – a

B – C | b

C – D

D – E

E – a

We have three unit productions.

B – C

C – D

D – E. we need to eliminate these three productions.

Here, B calls C and C calls D, D calls E, and E-checks for input symbol a.

So finally, C checks for input symbol a.

We replace the unit productions with input symbol a.

The below grammar shows the CFG after eliminating unit production.

S – AB

A – a

B – a|b

C – a

D – a

E – a

Example 2:

S – Aa | B

B – A | bb

A – a | bc | B

The unit productions are

S – B, B – A, and A – B

S is calling B, and B is calling A, and A is calling for B., so write all the possibilities.

The production S is written as

S – Aa | bb | a | | bc

Similarly, Write the remaining productions.

B – a | bc | bb

A – a | bc | bb

Example 3:

S – a | aA | B | C

A – aB | ε

B – Aa

C – cCD

D – ddd

First, we have to eliminate epsilon productions.

The below grammar shows the CFG after eliminating epsilon.

S – a | aA | B | C

A – aB

B – Aa | a

C – cCD

D – ddd

The below grammar shows the CFG after eliminating unit productions.

S – a | aA | Aa | cCd

A – aB

B – Aa | a

C – cCD

D – ddd