UGC NET CSE | January 2017 | Part 3 | Question: 22

Question

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 

• A. $\log_{K} \mid W \mid \leq h\leq \log_{K} \left (\frac{ \mid W \mid-1}{K-1} \right ) \\$
• B. $\log_{K} \mid W \mid \leq h \leq \log_{K} \left ( K \mid W \mid \right) \\$
• C. $\log_{K} \mid W \mid \leq h \leq K \log_{K} \mid W \mid \\$
• D. $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid – 1}{K-1} \right)$

Comments

is it option D?

Answer 1

Option D suits more appropriate than other option.

Comments

Explain it more better way.

Answer 2

It is a direct question , from peter linz

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

so D is correct answer here

Comments

Could you please explain with an example?