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

«
»
A unit production is a production A -> B where both A and B are non-terminals. Unit productions are redundant and hence should be removed. Follow the following steps to remove the unit production

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

S -> T and T -> F are the two unit productions in the CFG.
For productions T -> F we have F -> (S)/a so we add T -> (S)/a to the grammar and remove T-> F from the grammar. Now for production S -> T we have production T -> T * F/(S)/a so we add S -> T * F/(S)/a to the grammar. So the grammar after removal of unit production is:
S->S + T/ T * F/ (S)/ a
T -> T * F/ F
F -> (S)/ a

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.