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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.