Question

Remove all lambda-productions, unit-productions, and useless productions from the following grammar.

S -> AB | BC | aAb

A -> Aa | D | lambda

B -> aSC | bB | lambda

C -> aC | bBC

D -> abS | ab 

Answer 1

First, we have to remove useless productions. Two types of productions are called useless productions. a) The ones that cannot be reached from the starting symbol or b) the ones that cannot be terminated.

Production C is such a production. So we can remove that production. So the new production set is:

S -> AB | B | aAb
A -> Aa | D | λ
B -> aS | bB | λ
D -> abS | ab

Next, we have to remove Null productions.

First, we have to determine all the productions that can have Null productions. See productions for A & B are clear. But other productions can also derive Null productions, we need to find such productions. If we substitute B Null in S we get 2 new productions for S, similarly, we get 1 new production for D (i.e., ab which is already present for D).

S -> AB | B | A | aAb | λ
A -> Aa | D | λ
B -> aS | bB | λ
D -> abS | ab | λ

Now we finally have to remove Null production. We do so by substituting Null in all the ways possible and generate all the possible productions.

S -> A | B | AB | aAb | ab
A -> Aa | D | a
B -> aS | bB | a | b
D -> abS | ab

These are the productions that we get after removing Null productions.

Now, we have to remove Unit productions. To do so we use direct substitution.

S -> A | B | AB | aAb | ab
A -> Aa | D | a
B -> aS | bB | a | b
D -> abS | ab

First, we need to find what unit production can we derive from what symbols, just like we did for Null productions. So, we get:-

S -*-> A, S -*-> B, A -*-> D

where -*-> means after some unknown no. of steps.

Now, we need the original non-unit productions.

S -> AB | aAb | ab
A -> Aa | a
B -> aS | bB | a | b
D -> abS | ab

Now since S -*-> A, this means that we will ultimately at some point we may need to substitute for A if we start from S. So to remove that unit production we include all its values beforehand, & similarly for others, so we get new production set.

S -> a | b | ab | Aa | abS | aS | bB | AB | aAb
A -> Aa | abS | ab | a
B -> aS | bB | a | b
D -> abS | ab

The above grammar does not have any useless, Null, and unit productions.

Hope this helps. If you like the answer please upvote. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you.