retagged by
442 views

1 Answer

1 votes
1 votes

Remove Unit Productions

  1. $S \rightarrow aA | aBB$
  2. $A \rightarrow aaA | \lambda$
  3. $B \rightarrow bB | bbC$
  4. $C \rightarrow B$

'C' is a unit production, so replace it with B, whenever it occurs on RHS. So replacing C in production-3

  1. $S \rightarrow aA | aBB$
  2. $A \rightarrow aaA | \lambda$
  3. $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

  1. $S \rightarrow aA | a | aBB$
  2. $A \rightarrow aaA | aa $
  3. $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

  1. $S \rightarrow aBB$
  2. $B \rightarrow bB | bbB$

So, finally, we are left with below productions. This is mi

  1. $S \rightarrow aA | a $
  2. $A \rightarrow aaA | aa $

The language generated by grammar is $a(aa)*$ 

Related questions

0 votes
0 votes
2 answers
1
0 votes
0 votes
2 answers
4
suneetha asked Dec 22, 2018
326 views
i thought that it is the language where both start and end symbols are same and i got 65 but the ans is 29