[TOC] CNF Tree Depth

Question

1. Assume that we have CNF tree of depth of h(Assume root at height 0).What is the maximum yeild possible in terms of h?

2. Assume that we have a string of length n,what is the min and max height of parse tree possible in CNF.

Please explain

Answer 1

Refer the above image with example.

Answer 2

first lets let what are the basic properties of a CNF, say G={V,T,S,P}

1) production is in the form A->x or A->BC (where A,B,C are non terminals and x is a terminal)

2) whenever we say derivation we either mean left most derivation or right most...not haphazardly..

 

 

 

ANSWER FOR PART 1=>

 now it's intuitive that we can write a production of CNF like below---

P->Q where P belongs to V

         and Q belongs to T or Q is MN (M,N belongs to V)

so we can see its obvious that when we derive one sentential form from the previous one we either increment the number of non ternimals or we change one non terminal by a terminal.

say string length is |w| then from S (i.e. start symbol) we grow it to the length of |w| non ternimals and then one by one convert each non terminal to a terminal

so now at the start we have one length sentential form i.e. S

then we grow it to |w| and it takes |w|-1 rounds

at this time we have a all non terminal sentential form of length |w|

now we one by one change the non ternimals to terminals..

this takes more |w| rounds or steps..

so for a string of length |w| it requires 2×|w| - 1 rounds or steps to derive the string..

here u have given tree height h so

2*x-1=h

=>x=(h+1)/2

this is the maximum yield.

 

 

 

 

 

ANSWER FOR 2ND PART=>

for CNF as it has constraints over production as mentioned before its always 2*n-1 steps to get or to derive a string of length n

so max and min steps are both 2*n-1