615 views

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

1. $\log_{K} \mid W \mid \leq h\leq \log_{K} \left (\frac{ \mid W \mid-1}{K-1} \right ) \\$
2. $\log_{K} \mid W \mid \leq h \leq \log_{K} \left ( K \mid W \mid \right) \\$
3. $\log_{K} \mid W \mid \leq h \leq K \log_{K} \mid W \mid \\$
4. $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid – 1}{K-1} \right)$

### 1 comment

is it option D?

Option D suits more appropriate than other option.

### 1 comment

Explain it more better way.

It is a direct question , from peter linz

answer should be logkw <=h<= (|w|-1)/(k-1)

so D is correct answer here

### 1 comment

Could you please explain with an example?