GATE CSE 2013 | Question: 9

Question

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?

• A. $n/2$
• B. $n-1$
• C. $2n-1$
• D. $2^{n}$

Comments

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 )

A->a

B->b

C->c

D->d

E-> e

F->f

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.

---

@Aks9639 I think there is something wrong in the worst case example, u need to add one more production S->ABCDEF to get desired input string, hence accepted state 'ABCDEF' reduced to S. One more doubt, why you hadn't count accepted state move as a reduced move?

---

@Nitesh Singh 2 You are right but if in the it says A->a is unit production then you assume it and then find answer on behalves of this ,and right answer id n-1 by taking A->a as unit production.

Answer 1

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$

Comments

Don’t encourage these solutions.

You can’t just prove anything just by giving an example.

Please only upvote the solutions which directly equates to the solution in the perspective of problem setter.

---

@MiNiPanda

perfect explanation !

---

Here number of tokens must be 2

which are aa and bb......so number of tokens must be 2 not 4

Answer 2

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

Comments

nice expain

Answer 3

The answer is C.

Take,

S-->AB

A-->a

B-->b.

Derive ab. you'll have 3 reduce moves.

Comments

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.

Answer 4

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