GATE 2024 CS (CS2) – Question 40
Consider the CFG with start symbol S and terminals {a,b,c,d}: $S\to AaAb\mid BbBa$, $A\to cS\mid\epsilon$, $B\to dS\mid\epsilon$. In the partially-filled LL(1) table, S row has S→AaAb at a, S→BbBa at b, cells (1) at c and (2) at d; A row has A→ε at a, cell (3) at b, A→cS at c; B row has cell (4) at a, B→ε at b, B→dS at d. Which option represents the CORRECT combination for the numbered cells? ('blank' = empty)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) (1) $S\to AaAb$ (2) $S\to BbBa$ (3) $A\to\epsilon$ (4) $B\to\epsilon$
Explanation
Grammar: $S\to AaAb\mid BbBa$, $A\to cS\mid\varepsilon$, $B\to dS\mid\varepsilon$.
**FIRST sets of the S-productions:**
- $FIRST(AaAb)=\{c\}\cup\{a\}=\{a,c\}$ (since $A$ can vanish, `a` is first).
- $FIRST(BbBa)=\{d\}\cup\{b\}=\{b,d\}$.
So in the S row: column `c` (cell 1) $=S\to AaAb$ and column `d` (cell 2) $=S\to BbBa$ (columns a, b already agree).
**$\varepsilon$-productions use FOLLOW:**
- $FOLLOW(A)$: in $AaAb$ the first $A$ is followed by `a`, the second by `b`. So $FOLLOW(A)=\{a,b\}$, giving $A\to\varepsilon$ in column `b` (cell 3).
- $FOLLOW(B)$: in $BbBa$ the first $B$ is followed by `b`, the second by `a`. So $FOLLOW(B)=\{a,b\}$, giving $B\to\varepsilon$ in column `a` (cell 4).
No cell holds two productions, so the grammar is LL(1) and the filled table is (1) $S\to AaAb$, (2) $S\to BbBa$, (3) $A\to\varepsilon$, (4) $B\to\varepsilon$: option (A).