The Gateway to Computer Science Excellence
0 votes
176 views

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.

in Theory of Computation by Boss (35.7k points)
edited by | 176 views
0
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
@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
ok i understand but B is not nullable variable because it's not able to derive λ
0
Ohh sorry.. I thought u were talking about "B" which was mentioned in that image..
+1
so the answer should be

$S \rightarrow B|λ,$
$B \rightarrow aBb,$
$B \rightarrow b$.

am i correct?
+1
yes..

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,497 answers
195,493 comments
100,825 users