The Gateway to Computer Science Excellence

0 votes

A Grammer is said to be in 4-Standard form if all productions of the grammer are of type A → BCDE|a. If a grammer is in 4-Standard form how many steps in derivation of w will require if length of string w is 256 ?

0

Brother can u derive how do we get 2n-1 steps if the grammer is in CNF. i have a little doubt in it please :)

0

Same way.

To generate n non-terminals = n-1 steps.

To generate n terminals out of those n non-terminals = n steps.

Sum them up to get 2n-1 steps.

To generate n non-terminals = n-1 steps.

To generate n terminals out of those n non-terminals = n steps.

Sum them up to get 2n-1 steps.

+6

First make a series of Non terminals which length is 256, then for each step you can convert one non-terminal into one terminal.

===> Total steps required to generate 256 terminals from 256 Non-terminals = 256.

Now our problem is " How many steps required to generate a series of 256 Non terminals ? "

it is given 4-standard form, it means by one NON-Terminal, you get 4 Non-Terminals.

∴ gain from every step = 4 - 1 = 3 Non-terminals.

A ---> BCD** E** ( after 1st step you got 4 variables, i.e., 3 + 1 )

-----> BCD FGH__ I__ ( after 2st step you got 7 variables, i.e., 3 + 3 + 1 )

-----> BCD FGH JKLM ( after 3rd step you got 10 variables, i.e., 3 + 3 + 3 + 1 )

if you observe the pattern, it is like __ 3s+1__ variables after

to get 256 variables, let we need k steps, then

3k + 1 = 256 ==> 3k = 255 ==> K = 85

So, total steps = 85 + 256 = 341

0

bro I don't remember which particular test it belongs to, so I can't say for sure.

I guess the way you solved is the same way they had solved.

First by finding the number of steps to generate n non-terminals using AP formula, and then simply generate n terminals out of that in n steps.

52,345 questions

60,483 answers

201,812 comments

95,288 users