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

1,703

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?

Share:
1,703

Related videos on Youtube

ً       ً
Author by

ً ً

Updated on June 25, 2020

Comments

  • ً       ً
    ً ً over 3 years

    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)

    • Gerry Myerson
      Gerry Myerson about 8 years
      Can you edit the title so it gives some idea of what the problem is about?
    • ً       ً
      ً ً about 8 years
      @GerryMyerson , I edited
    • Gerry Myerson
      Gerry Myerson about 8 years
      No, you didn't. I asked you to edit the title so it gives some idea of what the problem is about. "Better approach to solve this problem?" could be about anything.
    • ً       ً
      ً ً over 7 years
      @GerryMyerson, I've edited title.
    • Gerry Myerson
      Gerry Myerson over 7 years
      Welcome back...