Eliminating Useless Productions

In this class, We discuss Eliminating Useless Productions.

For Complete YouTube Video: Click Here

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

We take examples and understand the elimination of useless productions.

Example 1:

S – aS | A | C

A – a

B – aa

C – aCb

To eliminate useless productions we need to check the following conditions.

Find variables that are not deriving terminals. I.e., not going to end.

Find variables not reachable from the start state.

The above grammar C – aCb production is not going to end.

The production C keeps on calling C.

Production B is not reachable from the start state.

The below grammar shows the CFG after eliminating useless productions

S – aS | A

A – a

Example 2:

S – AB | CA

B – BC | AB

A – a

C – aB | b

Production B is not going to end.

The production B is calling B itself. So remove the production.

The below grammar shows the CFG after eliminating useless productions.

S – CA

A – a

C – b

Example 3:

S – ABC | BaB

A – aA | BaC | aaa

B – bBb | a

C – CA | AC

The production C is not going to end. So we need to remove C.

The below grammar shows that the CFG, after eliminating productions.

S – BaB

A – aA | aaa

B – bBb | a

Now, we check for productions not reachable from the start state.

Production A is not reachable from the start state.

The below grammar shows the CFG after eliminating useless productions.

S – BaB

B – bBb | a