Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
\(\log_K|W| \le h \le \left(\dfrac{|W| - 1}{K - 1}\right)\)
Since every production has a right side of length exactly K > 1, every internal node of a derivation tree has exactly K children and there are no ∈-productions, so the leaves are exactly the |W| symbols of W.
Step 1 — Lower bound: a tree of height h with branching K has at most \(K^h\) leaves, so \(|W| \le K^h\), i.e. \(h \ge \log_K|W|\).
Step 2 — Count internal nodes: if there are i internal nodes, the tree has \(iK + 1\) nodes in total, of which \(iK + 1 - i\) are leaves. Hence \(|W| = i(K - 1) + 1\) and \(i = \dfrac{|W| - 1}{K - 1}\).
Step 3 — Upper bound: the longest root-to-leaf path passes through h distinct internal nodes, so \(h \le i = \dfrac{|W| - 1}{K - 1}\). This bound is reached by a “caterpillar” tree in which only one child per level is a variable.
The bounds that take a logarithm on the right, \(\log_K\left(\dfrac{|W|-1}{K-1}\right)\) and \(\log_K(K|W|) = 1 + \log_K|W|\), fail for the caterpillar tree, whose height grows linearly in |W|. The bound \(K\log_K|W|\) also fails: for K = 2 the caterpillar has height |W| – 1, which exceeds \(2\log_2|W|\) once |W| is moderately large.
\(\log_K|W| \le h \le \left(\dfrac{|W| - 1}{K - 1}\right)\) option is correct.
Similar Questions
The following Context-Free Grammar (CFG) :
S → aB | bA
A → a | as | bAA
B → b | bs | aBB
will generate
The context free grammar given by
\(S \to XYX\)
\(X \to aX \mid bX \mid \lambda\)
\(Y \to bbb\)
generates the language which is defined by regular expression :
A context free grammar for \(L = \{ w \mid n_{0}(w) \gt n_{1}(w) \}\) is given by :
If all the production rules have single non - terminal symbol on the left side, the grammar defined is :
Match the following :
List - I List - II a. Chomsky Normal form i. \(S \to b\,S\,S \mid a\,S \mid c\) b. Greibach Normal form ii. \(S \to a\,S\,b \mid ab\) c. S-grammar iii. \(S \to AS \mid a\)
\(A \to SA \mid b\)d. LL grammar iv. \(S \to a\,B\,S\,B\)
\(B \to b\)The context free grammar for the language \(L = \{a^{n}b^{m}c^{k} \mid k = |n - m|, n \geq 0, m \geq 0, k \geq 0\}\) is
For the above specified passage, which of the following represent the grammar for the language accepted the machine?
Which of the folowing CFG(s) is/are in chomsky Normal form (All capital letters are variables & lower case are terminals)
A. S → ABC / AB
A → a
B → b
C → dB. X → RT / TR
T → t
R → XT / rC. P → qP / sQ
Q → r / sD. M → MN / MP
N → nm / n
P → pChoose the correct answer from the options given below:
Important Questions from Context Free Grammars
- Which of the following Grammars is/are only Context Free?
A S $\rightarrow$ Ab
aS$\rightarrow$ aA
A$\rightarrow$ aB S $\rightarrow$ Ab
A $\rightarrow$ Sa
A $\rightarrow$ aC S $\rightarrow$ AS
S $\rightarrow$ aA
A$\rightarrow$ aD S $\rightarrow$ Ab
S $\rightarrow$ aA
A$\rightarrow$ aE S $\rightarrow$ Sb
A $\rightarrow$ Aa
A $\rightarrow$ $\varepsilon$
Choose the correct answer from the options given below: Which of the following grammars is (are)ambiguous ?
(1) S → SS | aSb | bSa |e(2) S → aSbS | bSaS |e
(3) S → aAB
A → bBb
B → A Ι eConsider the grammar,
G = S → abScB | e,
B→ bB | b.
What is the language generated by the given grammar ?
Consider the given grammar
S → Abc | adA → eS | Cr| ξ
C → f/p/ξ
Compute FIRST (A)Select the sentence which is meaningful and grammatically correct.
