GATE CS 1995 Q1.10 — Parsing (LL, LR)

To determine the type of the given grammar, we analyze the production rules:

• $S \rightarrow a \alpha b \mid b \alpha c \mid aB$
• $S \rightarrow \alpha S \mid b$
• $S \rightarrow \alpha b b \mid ab$
• $S \alpha \rightarrow bd b \mid b$

We observe the following:

1. The production $S \alpha \rightarrow bd b \mid b$ has a left-hand side ($S \alpha$) containing more than one symbol. In a Context-Free Grammar (CFG), the left-hand side of every production must be a single non-terminal. Thus, this grammar is not Context-Free.
2. Since it is not context-free, it cannot be Regular (Option B) or $LR(k)$ (Option D), as both are subsets of context-free grammars.
3. By elimination, the grammar is classified as Context sensitive (Option C).

Note on formal classification: Strictly speaking, the production $S \alpha \rightarrow b$ is length-decreasing ($|S \alpha| = 2 > |b| = 1$), which technically makes the grammar unrestricted (Type-0). However, among the given options, Option C is the intended choice.