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

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.

Answer 2

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 

ANSWER IS N-1 AND IT IS OPTION b

Answer 3

Let's take CNF as our benchmark. Productions in CNF are of the form:-

$A\rightarrow BC$ (allowed as per question)

$A\rightarrow b$ (not allowed as per question)

 

Since $A\rightarrow b$ isn't allowed, take two samples

• $A\rightarrow bb$
• $A\rightarrow bbb$

We know, CNF takes $2|w|-1$ steps to derive the string. => It takes $2|w|-1$ reductions.

 

Take

$A\rightarrow bb$ in modified CNF

Instead of deriving $w$ symbols in $2|w|-1$ steps, we actually derived $2w$ symbols in $2|w|-1$ steps. So for w symbols, we took $|w|-1$ steps.

 

Take

$A\rightarrow bbb$ in modified CNF

Instead of deriving $w$ symbols in $2|w|-1$ steps, we actually derived $3w$ symbols in $2|w|-1$ steps. So for $w$ symbols, we took $\frac{2|w|}{3}-1$ steps.

 

Clearly if we keep on adding terminals on the RHS, we'll keep getting lesser steps.

To maximise the number, $A\rightarrow bb$ is most suitable (as lower than that is illegal as per question)

 

And $A\rightarrow bb$ fused with CNF takes $|w|-1$ steps for w tokens, as already seen.

 

Option B

Comments

However, if the question asked the maximum number of strings for a grammar with no epsilon and unit-productions — without defining unit productions, the answer would be Option C.

Because no epsilon, and no unit productions are characteristics of CNF and GNF, out of which CNF takes more steps (2w-1; compared to GNF's w steps)

Answer 4

Since it is given that the grammar cannot have:
1) epsilon production
2) production of the form A → a
Consider the grammar:
S → Sa | a
If we were to derive the string “aaa” whose length is 3 then the number of reduce moves that would have been required are shown below:
S→ Sa
→Saa
→aaa
This shows us that it has three reduce moves. The string length is 3 and the number of reduce moves is also 3. So presence of such kinds of production might give us the answer “n” for maximum number of reduce moves. But these productions are not allowed as per the question.
Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed “n” where “n” denotes the length of the string.
3) No unit productions
Consider the grammar:
S→ A
A→ B
B→C
C→a
If we were to derive the string “a” whose length is 1 then the number of reduce moves that would have been required are shown below:
S→ A
A→ B
B→C
C→a
This shows us that it has four reduce moves. The string length is 1 and the number of reduce moves is 4. So presence of such kind of productions might give us the answer “n+1” or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.
Now keeping in view the above points suppose we want to parse the string “abcd”. (n = 4) using bottom-up parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving right most derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon- and unit-production (i.e., of type A → є and A → B) and no production of the form A→a) as follows:
S→aB
B→bC
C→cd
The Right Most Derivation for the above is:
S → aB (Reduction 3)
→ abC (Reduction 2)
→ abcd (Reduction 1)
We can see here the number of reductions present is 3.
We can get less number of reductions with some other grammar which also doesn’t produce unit or epsilon productions or production of the form A→a:
S→abA
A→ cd
The Right Most Derivation for the above is:
S → abA (Reduction 2)
→ abcd (Reduction 1)
Hence 2 reductions.
But we are interested in knowing the maximum number of reductions which comes from the 1st grammar. Hence total 3 reductions as maximum, which is (n – 1) as n = 4 here.