The Gateway to Computer Science Excellence
0 votes
191 views
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
in Theory of Computation by Boss (25.2k points)
retagged by | 191 views

1 Answer

0 votes
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
by (221 points)

Related questions

0 votes
1 answer
3
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
50,654 questions
56,170 answers
193,883 comments
94,316 users