GATE Computer Science (CS) 2020 Solved Papers

© examsiri.com

Question : 18 of 65

Marks: +1, -0

Consider the following grammar.

{S} → {aSB} ∣ {d}

{B} → {b}

The number of reduction steps taken by a bottom-up parser while accepting string aaadbbb is ______ .

Your Answer:

Solution:

{S} → {aSB}

→ {aaSBB}[ {S} → {aSB}]

\to

aaaSBBB [S

\to

aSB]

\to

aaad

{BBB}[ {S} → {d}]

→ aaadbBB[ {B} → {b}]

\to

aaadbbB

[ {B} → {b}]

\to

aaadbbb

[ {B} → {b}]

Total 7 steps required.

© examsiri.com

Go to Question:

Prev Question

Next Question