# Deriving epsilon with a context free grammar with epsilon rules

The below problem is from my Formal Languages class. The professor suggested drawing derivation trees for the language until we reach epsilon in all the leaves, and that it should begin to look like a geometric series. But I'm still having trouble getting started.

The way it was explained: if a context free grammar G contains epsilon rules and can reach epsilon, then show that it does so in N replacements, where N is <= the sum of a geometric series. What's the proof for showing an implication like this?  ## 1 Answer

Here's an example to get you started. Suppose our grammar had productions $$S\rightarrow TT\qquad T\rightarrow UU\qquad U\rightarrow \epsilon$$ so $l=2, m=3$.

Then, how fast can you get from $S$ to $\epsilon$? Clearly, it'll take 7 steps: $$S\Rightarrow TT\Rightarrow UUT\Rightarrow UUUU\Rightarrow UUU\Rightarrow UU\Rightarrow U\Rightarrow \epsilon$$ Notice that $(l^m-1)/(l-1)=(2^3-1)/(2-1)=7$.

What does the parse tree for this derivation look like? In particular, how many leaves will it have?

Now generalize this construction.