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
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?
Related videos on Youtube
ً ً
Updated on June 25, 2020Comments
-
ً ً 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?
- $n/2$
- $n-1$
- $2n-1$
- $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 about 8 yearsCan you edit the title so it gives some idea of what the problem is about?
-
ً ً about 8 years@GerryMyerson , I edited
-
Gerry Myerson about 8 yearsNo, 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 over 7 yearsWelcome back...