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

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?

1. $n/2$
2. $n-1$
3. $2n-1$
4. $2^n$

---

My attempt:

Let the grammar is:

$S→AB$

$A→aa |AB$

$B→bb |BA$

Let the string $w=aabb$ , string length is $4$ (say , $n$)

so, the required productions are : $S→AB$ ,$A→aa$ , $B→bb$ , number of production is $3 = n-1$

Can you explain it in a formal way, please?

This question(see-Q.no.-4) is from competitive exam GATE , and answer key is given option $n-1$ (see-q.no.-of-set-c)

Answer 1

Your answer is correct. However it does not prove that it is the maximum. It only says that there exist a grammar that use n-1 reduce move.

You should also prove that no grammar can use more.

Hint: Since there is no epsilon and unit production, what can you says on the number of letters when applying a reduce move?