Remove Unit Productions
- $S \rightarrow aA | aBB$
- $A \rightarrow aaA | \lambda$
- $B \rightarrow bB | bbC$
- $C \rightarrow B$
'C' is a unit production, so replace it with B, whenever it occurs on RHS. So replacing C in production-3
- $S \rightarrow aA | aBB$
- $A \rightarrow aaA | \lambda$
- $B \rightarrow bB | bbB$
Remove $\lambda$ expression
In production-2, $A \rightarrow \lambda$, create new production by replacing A with $\lambda$ whenever it occurs on RHS. So, replacing, in production-2 and production-1
- $S \rightarrow aA | a | aBB$
- $A \rightarrow aaA | aa $
- $B \rightarrow bB | bbB$
Remove Useless productions
Now, let us check for reach ability All productions are reachable from start symbol $S$.
Let us check for useless symbols. So collect terminals from productions which generate only terminals (as one of the production)
$a$ is generated by production-1 and production-2. So collect it
$\left \{ a \right \}$
Now, collect those non-terminals which generate above terminal on RHS. Production-1 and production-2
$\left \{ a, S, A \right \}$
Now, collect those non-terminals which generate above terminal and no terminals on RHS. No new production found.
So, now all those productions which generate terminals / non terminals other than those in above set, delete those productions
So, remove following
- $S \rightarrow aBB$
- $B \rightarrow bB | bbB$
So, finally, we are left with below productions. This is mi
- $S \rightarrow aA | a $
- $A \rightarrow aaA | aa $
The language generated by grammar is $a(aa)*$