The Gateway to Computer Science Excellence
+1 vote
222 views

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 Boss (30.2k points)
recategorized by | 222 views
0

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
50,644 questions
56,512 answers
195,560 comments
101,074 users