GATE CS 2024 Set 1 — Question 38

We are given the FIRST sets for the non-terminals:
$\text{FIRST}(S) = \{c, d, f\}$
$\text{FIRST}(T) = \{a, b, \epsilon\}$
$\text{FIRST}(R) = \{c, \epsilon\}$Let's analyze the incomplete productions based on these sets.1. Analyze Production (1) for $S$:
$S \rightarrow daT \mid \dots$
The production $S \rightarrow daT$ contributes $d$ to $\text{FIRST}(S)$.
The missing part (1) must contribute the remaining elements of $\text{FIRST}(S)$, which are $\{c, f\}$.

• Option (B) & (C): $S \rightarrow fR$. This starts with the terminal $f$. Thus, it adds $f$ to $\text{FIRST}(S)$, but it cannot add $c$. So, (B) and (C) are incorrect.
• Option (A) & (D): $S \rightarrow Rf$. Since $\text{FIRST}(R) = \{c, \epsilon\}$, this production adds $c$ (from $R \rightarrow c\dots$) and, because $R$ is nullable ($\epsilon \in \text{FIRST}(R)$), it also adds $\text{FIRST}(f) = \{f\}$. Thus, $S \rightarrow Rf$ contributes both $c$ and $f$. This matches the requirement.

2. Analyze Production (2) for $T$:
$T \rightarrow aS \mid bT \mid \dots$
The existing productions contribute $a$ and $b$ to $\text{FIRST}(T)$.
The missing part (2) must contribute $\epsilon$ to match $\text{FIRST}(T) = \{a, b, \epsilon\}$.

• Option (A): $T \rightarrow \epsilon$. This correctly adds $\epsilon$ to $\text{FIRST}(T)$.
• Option (D): $T \rightarrow cT$. This would add $c$ to $\text{FIRST}(T)$. However, $c$ is not in the given $\text{FIRST}(T)$. Thus, (D) is incorrect.

3. Analyze Production (3) for $R$:
$R \rightarrow \dots \mid \epsilon$
The existing production contributes $\epsilon$.
The missing part (3) must contribute $c$ to match $\text{FIRST}(R) = \{c, \epsilon\}$.

• Option (A): $R \rightarrow cTR$. This starts with $c$, satisfying the condition.

Therefore, Option (A) is the only one consistent with all the given FIRST sets.