2 edited tags
| link
1
source | link

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?

Problem definition

Derivation tree example