Exercise 7.5 p. 311

Exercise 7.5 p. 311

by MANUEL LOVO -
Number of replies: 1

Referring to exercise 7.5 on page 311 of the book, where one needs to find all nullable symbols, the following points are not clear to me:

1-Removing nullable symbols from CFG G, in the production D --> BB, do we also need to consider the subset that leads to D --> ε and consequently consider D as nullable?

2-If the answer to the previous question is yes, after finding the remaining nullable symbols, do we end up with the ε-production B --> ε again? In this case, do we simply conclude the algorithm by removing ε?"


In reply to MANUEL LOVO

Re: Exercise 7.5 p. 311

by Giorgio Satta -

In the construction to remove epsilon-productions from a CFG, one exception is mentioned in the textbook: do not remove all nonterminals symbols from the right-hand side, in case this leads to an epsilon-production.

Therefore epsilon-productions are never produced by the construction, they are only eliminated.