261 views
0 votes
0 votes
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}-1)}{(n-1)}$ steps. How close can you actually come to this bound$?$

Please log in or register to answer this question.

Related questions