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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,466 answers

195,381 comments

100,313 users