0 votes 0 votes 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 $\log_{K} \mid W \mid \leq h\leq \log_{K} \left (\frac{ \mid W \mid-1}{K-1} \right ) \\$ $\log_{K} \mid W \mid \leq h \leq \log_{K} \left ( K \mid W \mid \right) \\$ $\log_{K} \mid W \mid \leq h \leq K \log_{K} \mid W \mid \\$ $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid – 1}{K-1} \right)$ Theory of Computation ugcnetcse-jan2017-paper3 context-free-grammar theory-of-computation + – go_editor asked Mar 24, 2020 • recategorized May 24, 2020 go_editor 1.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply Sushant Gokhale commented Jan 31, 2017 reply Follow Share is it option D? 1 votes 1 votes Please log in or register to add a comment.
4 votes 4 votes Option D suits more appropriate than other option. HIMANSHU KUMAR 3 answered Jun 10, 2018 HIMANSHU KUMAR 3 comment Share Follow See 1 comment See all 1 1 comment reply Soham1 commented Oct 14, 2019 reply Follow Share Explain it more better way. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It is a direct question , from peter linz answer should be logkw <=h<= (|w|-1)/(k-1) so D is correct answer here Aboveallplayer answered Jan 31, 2017 Aboveallplayer comment Share Follow See 1 comment See all 1 1 comment reply Pushpa Singh commented Oct 3, 2017 reply Follow Share Could you please explain with an example? 0 votes 0 votes Please log in or register to add a comment.