The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+37 votes
3.9k views

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

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

4 Answers

+39 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
0
Just for the sake of knowledge. It is in CNF. and you must know how many steps does it take. Its 2n-1.
+49
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.
+6
ITS NOT CNF
+3
@arjun sir since the question defines unit production as A→a we can use any number of productions of form A→B
+4
@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.
0
@rahulkr

I think the approach u are using is not correct. Consider the following example:

A->BC

B->aaa

C->bbb

now suppose string is aaabbb

then

A->BC(reduction 3)

->aaaC(reduction 2)

->aaabbb (reduction 1)

n = 6

and number of reductions are 3 which is not n-1
+5
@anchit

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
0

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.

+14 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

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

Take,

S-->AB

A-->a

B-->b.

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

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

+3

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

+3

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

+4
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.
+2
thanks #GateKeeda :)
0

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"

0
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?
+1

@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

S->AB

B->CD

C->bb

D->cc

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

0
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.5k points)
Answer:

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

38,049 questions
45,543 answers
131,851 comments
48,879 users