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