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