GATE 2025 CS (CS2) – Question 40
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $G$ is LALR(1), not SLR(1)
Explanation
**1. Calculate FOLLOW(A).** From S → Aa, a can follow A; from S → bAc, c can follow A. Hence FOLLOW(A) = {a,c}.
**2. Exhibit the SLR conflict.** After reading d initially, an LR(0) state contains S → d·c and A → d·. SLR would shift on c for the first item and reduce A → d on every symbol in FOLLOW(A), including c. That is a shift/reduce conflict.
**3. Use the LR(1) lookaheads.** In that state, A → d· has lookahead only a, so it does not conflict with shifting c. After reading bd, the completed A item instead has lookahead c, while S → bd·a shifts a. These LR(0) cores differ, so LALR merging does not combine their conflicting lookaheads.
**4. Classify the grammar.** The relevant LR(1)/LALR actions are conflict-free, while SLR is not. **Answer: C — LALR(1), not SLR(1).**