Theory of Computation – Eliminating unit productions from the productions in the Context Free Grammar

Repeat the following steps while there is a unit production

1. Select a unit production A -> B, such that there exist a production B -> α, where α is a terminal
2. For every non-unit production, B -> α repeat the following step
   1. Add production A -> α to the grammar
3. Eliminate A -> B from the grammar

Example: Remove the unit productions from the following grammar
S -> AB
A -> a
B -> C / b
C -> D
D -> E
E -> a
Solution:
There are 3 unit production in the grammar
B -> C
C -> D
D -> E
For production D -> E there is E -> a so we add D -> a to the grammar and add D -> E from the grammar. Now we have C -> D so we add a production C -> a tp the grammar and delete C -> D from the grammar. Similarly we have B -> C by adding B -> a and removing B -> C we get the final grammar free of unit production as:
S -> AB
A -> a
B -> a / b
C -> a
D -> a
E -> a
We can see that C, D and E are unreachable symbols so to get a completely reduced grammar we remove them from the CFG. The final CFG is :
S -> AB
A -> a
B -> a / b

Question: Identify and remove the unit productions from the following CFG
S -> S + T/ T
T -> T * F/ F
F -> (S)/a
View Answer

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.
If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.