recategorized by
673 views
1 votes
1 votes

Let $G = (V, T, S, P)$ be a context-free grammar such that every one of its productions is of the form $A \rightarrow ν$, with $|ν| = k > 1$. The derivation tree for any string $W \in L (G)$ has a height such that

  1. $h < \frac{(|W|-1)}{k-1}$
  2. $\log_{k} |W| \leq h$ 
  3. $\log_{k} |W| < h < \frac{(|W|-1)}{k-1}$
  4. $\log_{k} |W| \leq h \leq \frac{(|W|-1)}{k-1}$
recategorized by

Please log in or register to answer this question.

Related questions

5 votes
5 votes
1 answer
3