Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no more than $\frac{\ell^m-1}{\ell-1}$ steps by which $A$ derives $\varepsilon$. How close to this bound can you actually come?

  • $\begingroup$ Please state the question in the title! That way it is easier to recognize for anyone who visits later. $\endgroup$ – reinierpost Jun 22 '20 at 9:05
  • $\begingroup$ Sorry, because this is my first time posting a question, I am not very skilled $\endgroup$ – pi leng Jun 22 '20 at 13:23
  • $\begingroup$ Hint, what happens when $m=1$? What happens when $m=2$? Restrict to small $\ell$ such as $\ell=2$ to ease exploration as well. $\endgroup$ – John L. Jun 23 '20 at 4:05

Your Answer

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

Browse other questions tagged or ask your own question.