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/2^{k} where n/2^{k} = 1

or, 2^{k} = n

or, k = log_{2}|w|.

So total steps = log_{2}|w| (for getting n non terminals) + 1 (for getting n terminals)

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?