GATE 2025 CS2 Q.40: solution and answer

Official answer: CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Compute the follow set: $A$ occurs in $S\to Aa$ and $S\to bAc$, so $\text{FOLLOW}(A)=\{a,c\}$.

2. Start state $I_0$ contains $S\to \cdot Aa$, $S\to \cdot bAc$, $S\to \cdot dc$, $S\to \cdot bda$ and $A\to \cdot d$. On $d$ it moves to $I_d=\{A\to d\cdot ,S\to d\cdot c\}$.

3. SLR(1) test on $I_d$: the reduce $A\to d$ is placed on every symbol of $\text{FOLLOW}(A)=\{a,c\}$, and the shift is on c. The entry for c holds both a reduce and a shift, a shift-reduce conflict, so $G$ is not SLR(1). (The state reached on $b$ then $d$ has the same problem on a.)

4. CLR(1) lookaheads in $I_d$: this $A\to d\cdot$ comes only from $S\to \cdot Aa$, so its lookahead is $\{a\}$. The reduce is on a and the shift is on c, so there is no conflict.

5. Reaching $d$ after $b$ gives $I_{bd}=\{A\to d\cdot ,S\to bd\cdot a\}$. Here $A\to d\cdot$ comes from $S\to b\cdot Ac$, so its lookahead is $\{c\}$, and the shift is on a. There is no conflict, so $G$ is CLR(1).

6. LALR(1) merges only CLR(1) states that have identical LR(0) cores. $I_d$ has core $\{A\to d\cdot ,S\to d\cdot c\}$ and $I_{bd}$ has core $\{A\to d\cdot ,S\to bd\cdot a\}$. The cores differ, so no states merge and the LALR(1) table equals the CLR(1) table, which is conflict-free.

7. Hence $G$ is LALR(1) (and CLR(1)) but not SLR(1). Option (B) is false because $G$ is LALR(1), (A) and (D) are false for the same reason or because $G$ is not SLR(1). The answer is (C).