The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+45 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?

  1. $n/2$
  2. $n-1$
  3. $2n-1$
  4. $2^{n}$
asked in Compiler Design by Veteran (406k points)
edited by | 5.9k views
But the grammar with unit production is of Form A-->B. i.e. a non terminal on the RHS.
This is straight from GATE paper :P
sir a/c to question we dont have to use either unit production or  A->a type production?
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.
If we have A-->B in the grammar, then more than (n-1) reductions are possible.

@vishalshrm539 yes exactly ... I think they should have also given that A->B type productions are not there in the grammar ... 

This question has Typing mistake because Unit production means A->B where A&B both are non-terminal and here a should have been B.
For the sake of simplicity we also take it as:

in a worst case  (because they asked only maximum )





E-> e


for n=6 token stream we takes abcdef

so for a,b,c,d,e we got 5 reduce moves and , last one for f we got accepted state thats not a reduced move so finally we got 6-1=>n-1 reduced moves.

if may be they asked about minimum then :

we can take production like  A-> abcdef

there is no reduced move only accepted state. (however there will be more shift moves...)

it is going to be 0.

6 Answers

+46 votes
Best answer

Ans will be B

  • $A \rightarrow BC$
  • $B \rightarrow aa$
  • $C \rightarrow bb$

Now suppose string is $aabb.$ Then

$A \rightarrow BC$ (reduction $3$)
$\quad \rightarrow aaC$ (reduction $2$)
$\quad \rightarrow aabb$ (reduction $1$)

$n = 4$ and number of reductions is $3.$ So, $n-1$

answered by
edited by
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 think the approach u are using is not correct. Consider the following example:




now suppose string is aaabbb


A->BC(reduction 3)

->aaaC(reduction 2)

->aaabbb (reduction 1)

n = 6

and number of reductions are 3 which is not n-1

max number of reductions is asked

so in ur example in a single sttep you are reducing more than 1 terminal which cannot give max value

only one terminal should be reduced in each step only then u get max number of reductions

Since it is not in CNF we can't take A->a but we can take A->aa i.e. two terminals. We could have taken three, four anything but to get the highest no. of reductions we consider two as one is not allowed.

Also to increase the number of reductions the productions should be in the form of X->YZ i.e. two non terminals reduced to 1.

Why don't we take X->Y form? I feel that if this was allowed then no. of reductions could have not been derived because lets say our productions are S->A, A->B, B->C, C->c. So no. of reductions needed to reduce "c"  to S is c->C-; C->B; B->A; A->S is 4. Now to get highest no. of reductions we can just keep on increasing this unit productions as much as we can i.e. S->A, A->B, B->C, C->D, D->E; E->c. So now to reduce c we take 6 reductions. So these unit productions cannot be considered here in our question. Hence we take X->YZ form.

Comparing it with the CNF's formula:

What we did in case of CNF: If "n" is the length of string, each character of the string can be reduced to one non terminal. So no. of non terminals obtained in the 1st reduction (in bottom up manner is "n" since one terminal reduced to exactly one non terminal) is "n". 

Now these "n" non terminals form the leaf nodes of a binary tree. Such binary tree(where every non-leaf node has 2 children i.e. productions are in the form of X->YZ) with n leaf nodes takes (2n-1) moves to reduce to the start symbol. 

Here in this question, two terminals  reduce to one non terminal

So n terminals reduce to n/2 non terminals. Now this binary tree contains  n' leaf nodes where n'=n/2.

As already mentioned, such binary tree takes (2n'-1) moves to reduce to start symbol so (2*n/2-1)=(n-1) moves is reqd.


@MiNiPanda correct & detailed explanation . Thanks

i think answer will be c

no @ it cant be it is only possible for if it is CNF where unit productions allowed

The minimum possible allowable grammar rules can be



Now suppose to derive a string of length $n$, $n-1$ steps are needed to get all non-terminals.Further, n steps would be required to expand each non-terminal to a terminal accounting to a total of $2n-1$ steps to derive a string of length $n$

But hold.Here we would get a string of length $2n$, so to derive a string of length $2n$, we made $2n-1$ steps.

Let $2n=k$, then to derive a string of length $k$, maximum steps we need is $k-1$
+18 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 :





Generate string of 5 tokens as





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

answered by Active (1.6k points)
+4 votes
The answer is C.





Derive ab. you'll have 3 reduce moves.
answered by Boss (19.9k points)

How do you come to the conclusion that this is the maximum possible number of reduce moves?


You take any Grammar of this form. The answer will be 2n-1.


but in the question it is given that production of the form Aa  is not allow.

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.
thanks #GateKeeda :)

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 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?

@vaishali    here they are not mention wheather we follow CNF or not just simply think that maximum how many step can we take to genearte a string without using any production A->a and unit production(A->B) and null production





A->aa so 5 steps required to generate 'aabbcc'

Thank you, I get it.
0 votes
Input length = n;

From backward 1st level reduce move = n/2;

2nd level reduce move = n/4;

3rd level reduce move = n/8;

and so on....

so total no of reduce move: n/2+n/4+n/8+n/18+......+1

which is equal to ~=n-1
answered by Active (2.3k points)
0 votes
Whatever you have learnt is Right, the problem is in the question itself-

This question has Typing mistake because Unit production means A->B where A&B both are non-terminal and here a should have been B.

so they did mistake and to make it right they answered on the basis of this question, that answer would be n-1. but to make it max. no of reduction you can take A->B, B->C, C->D.......which is correct so marks should have been given to all.

however according to standard epsilon & unit production removal the string can be generated in min. n-1 and max. 2n-1 reductions.
answered by Active (1.8k points)
0 votes

Since what can we conclude from this question is  to make parse tree we are not going to use any any null and  ONE length production .

Think like this we are trying to make the binary tree and there in not any single child internal node and 0 child .

0 child(leaf or symbol ) is only allowed at the bottom level . So now we have n leaf so to maximize the internal node(which is nothing but a reduction like A=ab) we will use only  those production (NOTE THAT NO INFO GIVEN ABOUT GRAMMAR SO YOUR CHOICE TO CHOOSE ANY GRAMMER )which will reduce two symbol to One (like S=AB) in such way we know that for a perfect binary tree if we have n leaf node then (n -1) internal node which is nothing but no of reduction so 


answered by (255 points)

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
49,541 questions
54,093 answers
71,001 users