GATE CS 2025 Set 2 | Question 40

MCQ · 2 marks · −0.66

Given a Context-Free Grammar \(G\) as follows:

\(S \to Aa \mid bAc \mid dc \mid bda\)

\(A \to d\)

Which ONE of the following statements is TRUE?

  1. Option A: \(G\) is neither LALR(1) nor SLR(1)
  2. Option B: \(G\) is CLR(1), not LALR(1)
  3. Option C: \(G\) is LALR(1), not SLR(1) (correct)
  4. Option D: \(G\) is LALR(1), also SLR(1)

Answer

(C)

Explanation

\(\text{FOLLOW}(A) = \{a, c\}\), since \(A\) is followed by \(a\) in \(S \to Aa\) and by \(c\) in \(S \to bAc\).

  • Not SLR(1). From the start state, reading \(d\) gives the items \(S \to d \cdot c\) and \(A \to d \cdot\). SLR reduces by \(A \to d\) on every symbol of \(\text{FOLLOW}(A)\), including \(c\), where the first item shifts: a shift-reduce conflict. The state after \(bd\) clashes the same way on \(a\).
  • LALR(1). With LR(1) lookaheads, \(A \to d \cdot\) has lookahead \(a\) only in the first state and \(c\) only in the second, so neither conflicts. No two LR(1) states share a core, so the LALR(1) table equals the conflict-free CLR(1) table.

So \(G\) is LALR(1) (and CLR(1)) but not SLR(1).

Answer: C