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

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

Since there is no proper mathematical form of reaching at the answer included in here, I am including mine.

For obtaining MAXIMAL number of reduce moves, we have to have 2 terminals / non-terminals from each root.

Something like

                  $A \rightarrow XY$

                  $X \rightarrow MN$

and so on..

Now we have n tokens in the expression. So we must have $\frac{n}{2}$ terminal sets which are reduced to non-terminals, assuming a set of 2 terminals is reduced to one non terminal.

These $\frac{n}{2}$ non terminals will then be reduced to $\frac{n}{4}$ non terminals and so on, till we reach the final 2 non terminals pointing to the one non terminal. The summation thus becomes:

                                       $\sum_{i=1}^{\inf}{\frac{n}{2^{i}}}$.

This becomes an infinite geometric series which can be evaluated as : $(n\frac{\frac{1}{2}}{1-\frac{1}{2}})-1$ as the last non-terminal is a single non-terminal and the root. Hence, option B

Answer 2

Here the intention of the question is also to exclude the productions of type $A\rightarrow B$.

Actually, if you can see the parse tree of any sentence that belongs to a grammar, every node will have at least 2 children except the leaves.

We can get the minimum number of reductions when a node has a vast number of children. i.e RHS of each production has more symbols.

Ex : $S\rightarrow abcde$, It takes only one reduction for string abcde

           S

     /  /  |   \  \

    a  b  c  d  e

As the number of children of an internal node in the parse tree increases(i.e RHS of each production), the number of reductions decreases.

Therefore, we’ll get the maximum number of reductions when every internal node has exactly 2 children in the parse tree. i.e RHS of every production has exactly 2 symbols.

Then every internal node represents a reduction.

If a string has n tokens, then the parse tree has n leaves

Then number of internal nodes (reductions) = n - 1

Ex :$S\rightarrow AB \\A\rightarrow aa \\B\rightarrow bb$

Parse tree of string aabb is 

                                  S

                                /     \

                              A       B

                            /    \     /   \

                          a      a   b    b

Answer 3

Lets take aabb and here rule is that  we cant  do reductions like A→ a or A→ epsilon

and they are asking for maximum reduce moves so as unit reduction will be not allowed so to get max lets start reducing 

two terminals  at once so that it doesnot violate above rules and give the chance to maximise

A->aa

B->bb

x->AB

aa reduced to A ---->1

bb reduced to B-------2

now we have AB

AB reduced to x---------3

 

aabb symbols 4

reductions 3

n-1

 

 

 

Answer 4

Lets take aabb and here rule is that  we cant  do reductions like A→ a or A→ epsilon

and they are asking for maximum reduce moves so as unit reduction will be not allowed so to get max lets start reducing 

two terminals  at once so that it doesnot violate above rules and give the chance to maximise

A->aa

B->bb

x->AB

aa reduced to A ---->1

bb reduced to B-------2

now we have AB

AB reduced to x---------3

 

aabb symbols 4

reductions 3

n-1