GATE CS 2004 Q88 — Parsing (LL, LR)

We can analyze the grammar by tracking how the number of $a$'s, denoted by $N_a(w)$, changes during derivations. The grammar is right-linear, which can be modeled as a state transition diagram where $S$, $A$, and $B$ represent states, and $b$-transitions do not change the state:

• From state $S$, generating an $a$ transitions to state $A$ ($S \rightarrow aA$).
• From state $A$, generating an $a$ transitions to state $B$ ($A \rightarrow aB$).
• From state $B$, generating an $a$ transitions back to state $S$ ($B \rightarrow aS$) or terminates with an $a$ ($B \rightarrow a$).

Thus, the states track the number of $a$'s modulo 3:

• State $S$ corresponds to $N_a(w) \equiv 0 \pmod 3$.
• State $A$ corresponds to $N_a(w) \equiv 1 \pmod 3$.
• State $B$ corresponds to $N_a(w) \equiv 2 \pmod 3$.

A derivation can only terminate in one of two ways:

1. Using $S \rightarrow b$, which occurs when the count of $a$'s is a multiple of 3 ($N_a(w) = 3k$).
2. Using $B \rightarrow a$, which adds one final $a$ to a state where $N_a(w) \equiv 2 \pmod 3$, resulting in $N_a(w) = 3k$.

Since $b$-productions ($S \rightarrow bS$, $A \rightarrow bA$, $B \rightarrow bB$) do not change the state, there is no restriction on the number of $b$'s. Thus, the language generated is $\{w \mid N_a(w) = 3k, k \in \{0, 1, 2, \dots\}\}$.