recategorized by
2,221 views

4 Answers

Best answer
17 votes
17 votes

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.

So,

$$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.$

Ref: http://web-ext.u-aizu.ac.jp/~hamada/AF/Compact-L5-Final-2.pdf 


Alternatively,

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$

edited by
1 votes
1 votes
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
–1 votes
–1 votes
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

Related questions

1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
4