Question

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 \, | \, BbBa \quad \quad A \to cS \, | \, \epsilon \quad \quad B \to dS \, | \, \epsilon \] The following is a partially-filled LL(1) parsing table. \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & \(a\) & \(b\) & \(c\) & \(d\) & \(\$\)
\hline \(S\) & \(S \to AaAb\) & \(S \to BbBa\) & (1) & (2) &
\hline \(A\) & \(A \to \epsilon\) & (3) & \(A \to cS\) & &
\hline \(B\) & (4) & \(B \to \epsilon\) & & \(B \to dS\) &
\hline \end{tabular} \end{center} 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.}

• (1) \(S \to AaAb\), (2) \(S \to BbBa\), (3) \(A \to \epsilon\), (4) \(B \to \epsilon\)
• (1) \(S \to BbBa\), (2) \(S \to AaAb\), (3) \(A \to \epsilon\), (4) \(B \to \epsilon\)
• (1) \(S \to AaAb\), (2) \(S \to BbBa\), (3) blank, (4) blank
• (1) \(S \to BbBa\), (2) \(S \to AaAb\), (3) blank, (4) blank

Hint:

To fill an LL(1) parsing table, use the FIRST and FOLLOW sets of the grammar rules for each non-terminal.

Answer 1

The Correct Option is A

For the given grammar and the parsing table:
Cell (1): This corresponds to the production for \(S\) when the input starts with \(c\). From the grammar, \(A \to cS\) and \(S \to AaAb\), leading to \(S \to AaAb\) in this cell. Hence, (1) is \(S \to AaAb\).
Cell (2): This corresponds to \(S\) when the input starts with \(d\). From \(B \to dS\) and \(S \to BbBa\), this cell contains \(S \to BbBa\). Hence, (2) is \(S \to BbBa\).
Cell (3): This corresponds to \(A\) when the input starts with \(b\). From the grammar, \(A \to \epsilon\), this cell contains \(A \to \epsilon\). Hence, (3) is \(A \to \epsilon\).
Cell (4): This corresponds to \(B\) when the input starts with \(a\). From the grammar, \(B \to \epsilon\), this cell contains \(B \to \epsilon\). Hence, (4) is \(B \to \epsilon\). The correct configuration for the cells is: \[ (1) S \to AaAb, \, (2) S \to BbBa, \, (3) A \to \epsilon, \, (4) B \to \epsilon. \] Final Answer: \[ \boxed{\text{(A)}} \]