The Gateway to Computer Science Excellence
+1 vote

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}$
in Theory of Computation by
recategorized by | 246 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,522 answers
95,372 users