Relationship Between SLR and LALR Parser State Counts ($n_1$ vs $n_2$)

In LR-family parsing, SLR(1) and LALR(1) both use the same underlying LR(0) state automaton (same viable-prefix sets / kernels), and differ only in how lookahead symbols are used to place reduce actions in the parse table. In particular, the LALR(1) simplification merges/represents LR(1) states with identical LR(0) cores, and this process yields an automaton whose number of states equals the LR(0) (hence equals the SLR(1)) state count. Therefore, for a grammar $G$, if the SLR parser has $n_1$ states and the LALR parser has $n_2$ states, we have: $n_1 = n_2$.3

A useful mental model is summarized by the hierarchy:

Here, LALR(1) is “more precise than SLR(1)” in its lookaheads, but it does not introduce additional LR(0) states—so the state count stays the same.2

Correct option: (i) $n_1 = n_2$.

Key concepts you need

• LR(0) core: LALR merges states with the same LR(0) core.
• Lookahead: affects reduce placement, not LR(0) state construction.
• FOLLOW set: used by SLR to place reductions.
• Merge by kernel: characteristic of LALR.

Why the state counts match ($n_1=n_2$)

• LALR(1) “merges rules that have identical kernel item sets” (LR(0) cores), because LR(0) state construction does not yet know lookaheads.
• LALR and SLR both correspond to using the same LR(0) viable-prefix state automaton; they differ only in lookahead computations for reductions.2
• Multiple sources explicitly state that LALR has the same number of states as SLR (and LR(0)), with LALR being more powerful than SLR but not increasing state count.3