GATE CSE 2024 | Set 1 | Question: 28

Question

Consider the following grammar $G$, with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by $(1), (2)$, and $(3)$.

$$\begin{aligned} & S \rightarrow d a T \mid \quad(1) \\ & T \rightarrow a S|b T| \quad(2) \\ & R \rightarrow(3) \mid \epsilon\end{aligned}$$

The set of terminals is $\{a, b, c, d, f\}$. The FIRST and FOLLOW sets of the different non-terminals are as follows.

$\begin{aligned} & \operatorname{FIRST}(S)=\{c, d, f\}, \operatorname{FIRST}(T)=\{a, b, \epsilon\}, \operatorname{FIRST}(R)=\{c, \epsilon\} \\ & \operatorname{FOLLOW}(S)=\operatorname{FOLLOW}(T)=\{c, f, \$\}, \operatorname{FOLLOW}(R)=\{f\}\end{aligned}$

Which one of the following options CORRECTLY fills in the incomplete productions?

• A. (1) $S \rightarrow R f$ (2) $T \rightarrow \epsilon$ (3) $R \rightarrow c T R$
• B. (1) $S \rightarrow f R$ (2) $T \rightarrow \epsilon$ (3) $R \rightarrow c T R$
• C. (1) $S \rightarrow f R$ (2) $T \rightarrow c T$ (3) $R \rightarrow c R$
• D. (1) $S \rightarrow R f$ (2) $T \rightarrow c T$ (3) $R \rightarrow c R$ 

Answer 1

Option $(C,D)$ is incorrect as if we substitute $T\rightarrow cT$ in $(2)$ it gives $FIRST(T)=a,b,c$ which is wrong because in  question it is given that $FIRST(T)=a,b,\epsilon$

Option $(B)$ is incorrect as if we substitute $S\rightarrow fR$ in $(1)$ it gives $FIRST(S)=f,d$ which is wrong because terminal $c$ is missing.

So correct Option is $(A)$.

$\begin{array}{|c|c|c|}\hline
&\textsf{FIRST}&\textsf{FOLLOW}\\\hline
S \rightarrow daT \mid Rf & \left \{ c,d,f \right \} & \left \{ \$,c,f \right \} \\\hline
T \rightarrow aS  \mid bS\mid \varepsilon & \left \{ a,b,\varepsilon \right \} & \left \{ \$,c,f \right \} \\ \hline
R \rightarrow cTR\mid  \varepsilon & \left \{ c,\varepsilon \right \} & \left \{ f \right \} \\\hline
\end{array}$