Skip to content
GATEiit

GATE CSE 2021 Set 2 Q61: Items in GOTO(GOTO(I0, <), <) for an LR(0) grammar

Question

Consider the following augmented grammar with {#,@,<,>,a,b,c}\{\#, @, <, >, a, b, c\} as the set of terminals.

S′→SS→S#cSS→SSS→S@S→<S>S→aS→bS→c\begin{aligned} S' &\rightarrow S \\ S &\rightarrow S \# c S \\ S &\rightarrow S S \\ S &\rightarrow S @ \\ S &\rightarrow < S > \\ S &\rightarrow a \\ S &\rightarrow b \\ S &\rightarrow c \end{aligned}

Let I0=CLOSURE({S′→∙S})I_0 = \text{CLOSURE}(\{S' \rightarrow \bullet S\}). The number of items in the set GOTO(GOTO(I0,<),<)\text{GOTO}(\text{GOTO}(I_0, <), <) is ________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 8 (official GATE 2021 final answer key)

Concept used: GOTO moves the dot over the symbol and then takes the closure.

First step: GOTO(I0,<)(I_0, <) contains S→<∙S>S \rightarrow < \bullet S > plus the closure items S→∙αS \rightarrow \bullet\alpha for all seven S-productions; apply GOTO on << again.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2021 Set 2 questions →