I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals:
- Basis: if $A \rightarrow \epsilon$ is a production, $A$ is nullable.
- Induction: if $A \rightarrow X_1X_2\ldots X_n$ is a production, and $X_1, X_2, \ldots, X_n$ are all nullable, then $A$ is nullable.
Intuitively, this algorithm seems correct. But I don't see how it could properly show $B$ to be nullable in the following grammar:
$$A \rightarrow a$$ $$A \rightarrow \epsilon$$ $$B \rightarrow B A$$
How does the algorithm deal with these recursive productions that are nullable? If not, what changes must be made to make it correct?
My second question is whether the following grammar is nullable, or whether it's even a valid context-free grammar at all.
$$S \rightarrow S$$