in Theory of Computation
2,884 views
7 votes
7 votes
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G

(a) log2|w|+1 (b) log2|w|
(c) log2|w|−1 (d) None of these
in Theory of Computation
2.9k views

3 Comments

$log_2$|w|
1
1
answer given is a , i am not getting it what is answer need explanation
0
0
TOC+ DS  what reasoning
0
0

4 Answers

12 votes
12 votes

All the CNF productions are in the form :

A --> BC(maximum 2 non terminal)

B --> a(terminal)

C --> b(terminal)

So, it is seen than to derive a terminal we need one step (Ex: B --> a). Also a non-terminal can derive maximum 2 non-terminals. (Ex: A-->BC).

Ok, let's say we have a string 'ab'. Now 'a' can be derived from B and 'b' can be derived from C.

               A

           /       \       (One step)

       B             C

       |              |    (One step)

       a              b

So, one step is used to derive a and b from B and C.

Now, we have two non-terminals. These two can be derived in one step in best case as A --> BC.

Generally, if we have |w| = n, then one step is needed for generating all the terminals from non-terminals.

Now we have 'n' non-terminals. To derive these n non-terminal we need n/2 non-terminals in the above level because every non-terminal can derive maximum 2 non-terminals.

Again to derive these n/2 non-terminals we need (n/2)/2 = n/4 non terminals. This step continues until it reaches to one non-terminal which is the start symbol. So n/2,n/4,n/8,.....,n/2k where n/2k = 1

or, 2k = n

or, k = log2|w|.

So total steps = log2|w| (for getting n non terminals) + 1 (for getting n terminals)

= log2|w| + 1

= total height

  Option (A)

2 votes
2 votes

All production in CNF are in the following forms:

S--->AB

S---->a {terminal}

Take any simple CNF :

S-----> AB

A---->a

B---->b

w=ab      |w|=2 , then height of tree is 2.

option A satisfies log|w|+1

4 Comments

thanks but if height is |w| then why answer has + 1 in it?
0
0

log2|w|+1 = log2 2 +1 = 1+1 =2

1
1
thanks :)
0
0
just follow the properties like CNF has maximum 2 desecendent
0
0
2 votes
2 votes

Assuming |w| = n.

So basically it requires n-1 steps to get n non-terminals and requires n steps to replace non terminals with terminals. So, in total 2n-1 steps. Now, at height 0, non-terminal = 1, at height 1 non-terminals = 2, at height 2 non-terminals = 4. So, at height k i.e 2 ^ k non - terminals will be n. So, 2 ^ k = n => k = logn but now we require n steps to replace non terminals with terminals, so it requires n steps but height will be increased by 1 only. Therefore k + 1 => logn + 1. As we assumed n = |w|, height = log|w| + 1

Can any please let me know if this approach is correct?

1 comment

Yes it is correct.
0
0
0 votes
0 votes

From peter Linz

option B is correct as you have binary Tree

for k-ary tree

it is

log to the base k (w)

Related questions