number of steps in derivation

Question

Answer 1

THEORETICALY:

Since, given grammar is not in CNF we need to Convert CFG to CNF !

On conversion of CFG to CNF of the given grammar will change from 5 production to 10  productions.

Now we need to generate string W using these 10 CNF production. we would get 19 productions 

DIRECTLY:

Will be using as for CNF as per formula  #PRODUCTIONS=2*length of string-1  {where length of string is 10}

                                                                                     =19 PRODUCTIONS

Comments

but formula is

If G is a Context Free Grammar in the Chomsky Normal Form, then for any string w belongs L(G) of length n ≥ 1, it requires exactly 2n-1 steps to make any derivation of w.

 

so it should be 19

---

What we are supposedto do theoretically :

1. Given grammar should be converted into CNF (Chomsky normal form) firstly, as mentioned in question.
2. Then drive the "string w" on the basis of CNF productions &  meanwhile should count no. of production used.

BUT we can do this directly :

1. Its given in question that string w is generated by CFG with CNF
2. Hence, for CNF  we have  formula No.of PRODUCTION= 2*length of string-1   {where length of string w  is 10}
3. We get No.of PRODUCTION= 2*10-1 =19

*********************FINAL ANSWER IS 19 PRODUCTIONS*****************************

---

@DEBASMITA 

given grammar is not in CNF you need to Convert CFG to CNF !

On conversion of CFG to CNF of the given grammar will change from 5 production(as given in question) to 10  productions.

Now you need to generate string W using these 10 CNF production. You will definately get 19 productions