GATE CS 2024 Set 2 | Question 40

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$.

$S \to AaAb \mid BbBa$
$A \to cS \mid \epsilon$
$B \to dS \mid \epsilon$

The following is a partially-filled LL(1) parsing table.

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, “blank” denotes that the corresponding cell is empty.

Option A: (1) $S \to AaAb$ (2) $S \to BbBa$ (3) $A \to \epsilon$ (4) $B \to \epsilon$ (correct)
Option B: (1) $S \to BbBa$ (2) $S \to AaAb$ (3) $A \to \epsilon$ (4) $B \to \epsilon$
Option C: (1) $S \to AaAb$ (2) $S \to BbBa$ (3) blank (4) blank
Option D: (1) $S \to BbBa$ (2) $S \to AaAb$ (3) blank (4) blank

Answer

(A)

Fill each cell from FIRST and FOLLOW sets.

$\text{FIRST}(A) = \{c, \epsilon\}$, so $\text{FIRST}(AaAb) = \{c, a\}$: $S \to AaAb$ goes under $a$ and under $c$, which is cell (1).
$\text{FIRST}(B) = \{d, \epsilon\}$, so $\text{FIRST}(BbBa) = \{d, b\}$: $S \to BbBa$ goes under $b$ and under $d$, which is cell (2).
In $S \to AaAb$ the two $A$s are followed by $a$ and by $b$, so $\text{FOLLOW}(A) = \{a, b\}$ and $A \to \epsilon$ fills both the $a$ column and cell (3).
Likewise $\text{FOLLOW}(B) = \{a, b\}$ from $S \to BbBa$, so $B \to \epsilon$ fills cell (4).

No cell receives two entries, so the grammar is LL(1) and none of the numbered cells is blank; swapping (1) and (2) would mix up the FIRST sets.

Answer: A

	\(a\)	\(b\)	\(c\)	\(d\)
\(S\)	\(S \to AaAb\)	\(S \to BbBa\)	(1)	(2)
\(A\)	\(A \to \epsilon\)	(3)	\(A \to cS\)
\(B\)	(4)	\(B \to \epsilon\)		\(B \to dS\)