crowso
crowso

Reputation: 2087

transform grammar problem

S -> aB | lamda
B -> bB

B is a useless production. Now after its removal

S -> a | lamda

Is this correct ?

Upvotes: 2

Views: 64

Answers (2)

par
par

Reputation: 17724

Boy it's been a long time since I've looked at CFG's. B produces an infinite series of b's, does it not (b*?)

Assuming b* means an infinite series of B's I think I would reduce to:

S -> ab* | λ

EDIT:

Yes, my answer above is wrong. The definition of a "useless production" is a production that is never used in the derivation of a terminal string. Since B is non-terminal it can be removed thus S -> λ.

+1 to the answer by user574183.

Upvotes: 1

user574183
user574183

Reputation: 716

production S -> aB does not terminate. Because B -> bB does not terminate. So the production S -> aB is useless.

the answer should be

S -> lambda

Upvotes: 2

Related Questions