# Nullable nonterminals and recursion

I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals:

1. Basis: if $A \rightarrow \epsilon$ is a production, $A$ is nullable.
2. 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$$

• Please don't ask two questions at once. – Yuval Filmus Dec 3 '15 at 11:37

A nonterminal $X$ is nullable if there is some derivation $X \to^* \epsilon$. It is clear that all non-terminals found by your algorithm are nullable (you can prove this by induction). On the other hand, if $X$ is nullable then take a derivation tree for the derivation, and prove by induction on the depth that all non-terminals on the way are recognized as nullable by this algorithm. This is why the algorithm is correct.
In your first example, $B$ is not nullable. In fact, you can't generate any string from $B$. The same is the case for your second example $S\to S$, where again the grammar generates no strings.
• Ohh, I got confused. Of course $B$ can't generate strings - it can never terminate... – orlp Dec 3 '15 at 12:10