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 ?
in Theory of Computation by | 168 views
Please give general method to solve such questions :)
The one given in their solution is the most general I found
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 :)
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.
should be 256+256+64+16+4+1 = 597

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 ---> BCDE    ( after 1st step you got 4 variables, i.e., 3 + 1 )

  -----> BCD FGHI    ( 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 s steps.

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

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

So, total steps  = 85 + 256 = 341



forget to ask, what is the answer they provided ?


@Shaik Masthan

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.

ok... either none of the thee members who participated in the discussion either commented or upvoted the comment !

So i thought, asking confirmation is better :)
Okay.. sorry from my side. :) I will take care of it from now on.
no, i didn't mean that !

Please log in or register to answer this question.

Related questions

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
52,345 questions
60,483 answers
95,288 users