Consider the following augmented grammar with \(\{ \#, @, <, >, a, b, c \}\)…
2021
Consider the following augmented grammar with \(\{ \#, @, <, >, a, b, c \}\) as the set of terminals.
\(\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \rightarrow SS \\ S \rightarrow S @ \\ S \rightarrow < S > \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow c \end{array}\)
Let \(I_0 = \text{CLOSURE}(\{S’ \rightarrow \bullet S\})\) The number of items in the set \(\text{GOTO(GOTO}(I_0<), <)\) is ___________.
Attempted by 95 students.
Show answer & explanation
Correct answer: 8
Key idea: compute closures and GOTO steps. Moving over '<' repeatedly leads to the same state, so the size stabilizes.
I0 = CLOSURE({S' → • S}) contains the items:
S' → • S
S → • S#cS
S → • SS
S → • S@
S → • < S >
S → • a
S → • b
S → • c
GOTO(I0, '<'): the only item with dot before '<' is S → • < S >. Moving the dot gives S → < • S >, and taking closure adds all productions with dot before S (the same seven S → • ... items). So GOTO(I0, '<') contains these 8 distinct items:
GOTO(GOTO(I0, '<'), '<'): in that set the only item with dot before '<' is again S → • < S >, so moving the dot produces S → < • S > and closure yields the identical set of 8 items. Therefore the number of items is 8.
Answer: 8
A video solution is available for this question — log in and enroll to watch it.