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$
$\endgroup$
3
-
$\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
Add a comment
|
