in Theory of Computation recategorized
544 views
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 

  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)$
in Theory of Computation recategorized
544 views

1 comment

is it option D?
1
1

2 Answers

4 votes
4 votes

Option D suits more appropriate than other option.

1 comment

Explain it more better way.
0
0
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

1 comment

Could you please explain with an example?
0
0
Answer:

Related questions