Repeat the following steps while there is a unit production

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

- 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

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.