The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes

Number of nodes in the derivation tree when a word of length $2^{k}$ is derived from a grammar in CNF?

  1. $2^{k+1} -1$
  2. $3.2^{k+1} - 1$
  3. $2^{k+1} + 1$
  4. $2^{k+1} + 1$
asked in Theory of Computation by Active (2.1k points)
recategorized by | 898 views

4 Answers

+16 votes
Best answer

In CNF, every production is of the form 

  1. $A \to BC$
  2. $A \to d$ ($d$ is a terminal). 

We are given a word of length $2^k$ meaning we reached $2^k$ terminals during parsing. If we consider the start symbol as root, the parse tree will be a strict binary tree (need not be a complete binary tree, a strict binary tree is a binary tree where every non-leaf node has two children) till the second last level with $2^k$ nodes and in last level  we have $2^k$ leaf nodes corresponding to the terminals. So, our problem now reduces to the number of nodes in a strictly binary tree with $2^k$ leaf nodes. 

If you know the property of strict binary tree answer is $2^{k+1} - 1$ and adding the $2^k$ leaf nodes we get the required answer as $3.2^k - 1$ nodes. Otherwise we can see the binary tree till the second last level as a graph with $n$ nodes and $n-1$ edges. We have $2^k$ nodes of degree 1 (leaf nods), a root node of degree 2 and $n - 2^k$ nodes of degree 3. So, sum of degrees $= 2^k + 2 + 3. (n - 2^k - 1)$.

In a graph, sum of degrees = 2. number of edges.


$$2^k + 2 + 3.(n - 2^k - 1) = 2(n-1) \\\implies n = 2.2^k - 1 = 2^{k+1} - 1. $$

Adding the $2^k$ leaf nodes we get the number of nodes as $3.2^k - 1.$



Number of derivation steps for a string of length $n$ from a grammar in CNF is given by $2n-1$. Here, $n=2^k$. So, number of derivation steps $=2\times 2^k - 1 = 2^{k+1} -1.$ To get the total number of nodes, we can add the $2^k$ leaf nodes to get $2^{k+1} - 1 + 2^k = 3.2^k -1$

answered by Veteran (414k points)
edited by

Arjun Sir, I think there is one important point missing here.

WLOG, let G be a CFG in CNF of the form -

$$A \rightarrow BC$$

$$A \rightarrow x$$

In the derivation tree of string $w\ \epsilon \ L(G)$, there will be an extra level for the production of the form $A \rightarrow x$

Which means that other than $2^{k+1}-1$ nodes in the tree there will be extra $2^k$ nodes in the last level of the derivation tree.

$\therefore n = 2^{k+1}-1 + 2^k$

$\implies 3*2^k - 1$

Please let me know if I am going wrong somewhere.

@prateekdwv I think u r right
@arjun sir what about the point mentioned by prateekdwv ?? we have to consider derivation of A->x at last stage or not ?
Yes, Thanks for pointing out. Fixed now.
+1 vote
The derivation tree for a CNF grammer is like binary tree as each production give 2 Non terminals till the last level has exactly same number of nodes as that of the word. The last level then gives only one terminal after which it gets complete.

So this can be solved as the number of nodes in a binary tree where there are $2^{k}$ leaf nodes. Then the final step where every leaf non terminal produces a terminal. Hence $2^{k+1} -1$ non terminals in the tree + $2^{k}$ terminals
answered by (317 points)
tree is complete?
Till we derive non terminal tree is complete. The derivation of terminal isn't.
I dont think so. Consider the root having 2 child nodes and say the left child can go to n level and right child stop after 1.
+1 vote
answered by Active (1k points)
thanks sir
–1 vote
c cnf means V->VV and V->T

V= variable T= terminal

so while making its tree

at root level (0th level)-  2^0 nodes

root+1 level - 2^1 nodes

like wise at kth level 2^k nodes

all these nodes vil contain only variables and last level vil be replaced by all terminals V->T therefore it vil contain 2^k nodes at k+1 level


(2^0+2^1+2^2+.......2^k)+2^k = (2^k)(3/2)-1 solve geometric progression that is option b
answered by (39 points)
How can you assume tree is complete?
if ul nt even considr complete tree it will nearly give u that answer becoz of cnf property

Related questions

+1 vote
1 answer
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
49,814 questions
54,521 answers
75,427 users