0 votes 0 votes Consider the grammar G with Productions $S \rightarrow A|B,$ $A \rightarrow λ,$ $B \rightarrow aBb,$ $B \rightarrow b$. Construct a Grammar $\hat{G}$ by applying the algorithm in Theorem 6.3. Theory of Computation theory-of-computation simplification peter-linz peter-linz-edition4 + – Mk Utkarsh asked Mar 23, 2018 • edited Mar 4, 2019 by Naveen Kumar 3 Mk Utkarsh 773 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Mk Utkarsh commented Mar 23, 2018 reply Follow Share I know null productions cannot be removed from this grammar because λ is in the language but i'm confused by the explanation of the algorithm. In the given grammar B is not nullable. The last statement says that if all $x_{i}$ are nullable, the production $A \rightarrow λ$ is not put into $\hat{P}$. Then from given grammar A is not in the $\hat{P}$. Need explanation in detail 0 votes 0 votes ankitgupta.1729 commented Mar 23, 2018 reply Follow Share @Utkarsh, this theorem is applicable only when λ is not in our language.. So our grammar will be S - - - > λ | aBb | b ; B - - - > b ... Now, in the given explanation, variable B should also be nullable.. Because B is generating all the variables which are already nullable.. So, B should also be included in the set of nullable variables.. Bcoz nullable means which can generate λ.. Now, for the last statement consider the following grammar :- S - - - > aA A - - - > BC B - - - > b | λ C - - - - > c | λ Since B and C are nullable.. So A will also be nullable.. So, here all Xi are nullable.. So, A----> λ will not be included in the new grammar according to rule.. So new production set will be S - - - > a | aA A - - - > B | C | BC B - - - > b C - - - - > c 0 votes 0 votes Mk Utkarsh commented Mar 23, 2018 reply Follow Share ok i understand but B is not nullable variable because it's not able to derive λ 0 votes 0 votes ankitgupta.1729 commented Mar 23, 2018 reply Follow Share Ohh sorry.. I thought u were talking about "B" which was mentioned in that image.. 0 votes 0 votes Mk Utkarsh commented Mar 23, 2018 reply Follow Share so the answer should be $S \rightarrow B|λ,$ $B \rightarrow aBb,$ $B \rightarrow b$. am i correct? 1 votes 1 votes ankitgupta.1729 commented Mar 23, 2018 reply Follow Share yes.. 1 votes 1 votes Please log in or register to add a comment.