3.3k 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}$
edited | 3.3k 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 ...

Ans will be B

$A \rightarrow BC$

$B \rightarrow aa$

$C \rightarrow bb$

now suppose string is $aabb$

then

$A \rightarrow BC$ (reduction $3$)

$\rightarrow aaC$ (reduction $2$)

$\rightarrow aabb$ (reduction $1$)

$n = 4$

and number of reductions are $3$ so $n-1$

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.
ITS NOT CNF
@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.
@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
@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

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

Take,

S-->AB

A-->a

B-->b.

Derive ab. you'll have 3 reduce moves.

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

@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'

Thank you, I get it.
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