The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+35 votes

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilon$ and $A \rightarrow a$) to parse a string with $n$ tokens?

- $n/2$
- $n-1$
- $2n-1$
- $2^{n}$

Question ask for number of reduce move. for bottom up parsing number of reduce move is equal to the number of internal node. answer does not change for A > a or A > aa is present in production.

+35 votes

Best answer

Just for the sake of knowledge. It is in CNF. and you must know how many steps does it take. Its 2n-1.

Here, in this question we are not supposed to have A -> a, even though that is not a unit production. Obviously a mistake in question, but we must follow what is written in question. Answer to this question is n-1, as given by GATE key. So, if similar thing happens in GATE, follow the question word by word and never try to correct the question.

@arjun sir since the question defines unit production as A→a we can use any number of productions of form A→B

@arjun sir,

I have same doubt if we use question data we can use as many productions of type A->B, the number of reduce moves won't be n-1, I guess.

I have same doubt if we use question data we can use as many productions of type A->B, the number of reduce moves won't be n-1, I guess.

+11 votes

Answer B option.

To get maximum number of Reduce moves, we should make sure than in each sentential form only one terminal is reduced. Since there is no unit production, so last 2 tokens will take only 1 move.

So To Reduce input string of n tokens, first Reduce n-2 tokens using n-2 reduce moves and then Reduce last 2 tokens using production which has . So total of n-2+1 = n-1 Reduce moves.

Example for this could be :

S-->aA

A-->bB

B-->cC

C->de

Generate string of 5 tokens as

S-->aA

-->abB

-->abcC

-->abcde

So first we take 3 steps to reduce ' abc ' and then take 1 step to produce ' de '. So total (5-2) + 1 = 4 Reduction moves

+3 votes

see my comment on the question. That's a mistake actually.

Unit productions are of type

A-->B. there shouldn't be any terminal on the RHS.

Unit productions are of type

A-->B. there shouldn't be any terminal on the RHS.

here i m taken each possible case. case1-> A->epsilon(Null prod) and A-> B (Unit prod.) not allowed then for 'n' length token how many **maximum** reduce move required . lets take example - for string 'ab' S->AB : A->a , B->b then here required 3 reduced moves . lets take other string ex- abc for that i do S->AB , A->DE , D->a , E->b ,B->c so it is 5 so we can say in general answer will be 2n-1

case 2 . if A-> epsilon(Null prod) and A-> a are not allowed but unit production allowed then for that if i take string 'ab' then for that S->A , A->B, C->D, D->E and so on ..at last producion i write like as K->ab so here for that we can't write a general form .

case3. if A-> epsilon(Null prod) and A-> a are not allowed and also unit production not allowed then take string 'ab' for that you can write only S->ab for that required 1 reduce and for string 'abcd' we can write S->AB , A->ab ,C->cd so required 3 so in general required 'n-1' reduce . then according to arjun sir no need to be change the question so i m going wid "n-1"

If grammar is S->BAC ,A->aa ,B->bb and C->cc then for generating aabbcc we need 4 steps.

is grammar should be in cnf?

is grammar should be in cnf?

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,801 users