[Solved]: Nullable nonterminals and recursion

Problem Detail: 

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$$

Asked By : orlp

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50255

3.2K people like this

 Download Related Notes/Documents