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.
- Buy Automata Theory Books
- Buy Computer Science Books
- Apply for Computer Science Internship
- Apply for Automata Theory Internship
- Practice Computer Science MCQs