Gateforum TOC Assessment test closed

Question

I want to know logic behind this,thanks in advance.

Comments

https://gateoverflow.in/576/gate1992_02-xviii

---

B) 2n-1

In CNF grammar is of the form A -> BC/a which means there will be only two variables on the right hand side of the production or terminal. 

Now take an example :

A --> BC/a

B --> b

C -->c

Generate the string bc using this grammar as :

A -->BC

  --> bC

  --> bc

so 3 steps for the string of length 2. With this all options other than B will be eliminated.

Let us take another example :

A-->BC/a

B-->CD/b

C-->DE/c

D-->d

E-->e

Produce string dedde using the above grammar :

A -->BC

  --> CDC

   --> DEDC

  --> DEDDE

  ---> dEDDE

 --> deDDE

  --> dedDE

  --> deddE

  --> dedde 

which took 9 steps to produce the string. So in genera it takes n-1 steps to get each variable in the right hand side + n more steps to get the yield. So in total it takes 2n-1 steps.

---

Thanks!