0 votes 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 ? Theory of Computation theory-of-computation parsing + – Na462 asked Jan 12, 2019 Na462 663 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Na462 commented Jan 12, 2019 reply Follow Share Please give general method to solve such questions :) 0 votes 0 votes aambazinga commented Jan 12, 2019 reply Follow Share The one given in their solution is the most general I found 0 votes 0 votes Na462 commented Jan 12, 2019 reply Follow Share 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 votes 0 votes aambazinga commented Jan 12, 2019 reply Follow Share 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. 0 votes 0 votes balchandar reddy san commented Jan 12, 2019 reply Follow Share should be 256+256+64+16+4+1 = 597 0 votes 0 votes Shaik Masthan commented Jan 12, 2019 reply Follow Share 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 7 votes 7 votes Shaik Masthan commented Jan 31, 2019 reply Follow Share @aambazinga forget to ask, what is the answer they provided ? 0 votes 0 votes aambazinga commented Jan 31, 2019 reply Follow Share @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. 0 votes 0 votes Shaik Masthan commented Jan 31, 2019 reply Follow Share 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 :) 0 votes 0 votes aambazinga commented Jan 31, 2019 reply Follow Share Okay.. sorry from my side. :) I will take care of it from now on. 0 votes 0 votes Shaik Masthan commented Jan 31, 2019 reply Follow Share no, i didn't mean that ! 0 votes 0 votes Please log in or register to add a comment.