GATE CS 2016 Set 1 Q42 — Context-free Grammars and Push-down Automata

To find the languages generated by the context-free grammars $G_1$ and $G_2$, let us analyze them step-by-step:

1. Analysis of $G_1$

The grammar $G_1$ is given by:

$$\begin{aligned} S &\to aS \mid B \\ B &\to b \mid bB \end{aligned}$$

• The variable $B$ generates one or more $b$'s: $$B \Rightarrow b^+ = \{b^n \mid n \ge 1\}$$
• The start symbol $S$ can generate any number of $a$'s followed by $B$: $$S \Rightarrow a^* B \Rightarrow a^* b^+$$

In set notation, this is represented as: $$L(G_1) = \{ a^m b^n \mid m \ge 0 \text{ and } n > 0 \}$$ This immediately eliminates options A, B, and C.

2. Analysis of $G_2$

The grammar $G_2$ is given by:

$$\begin{aligned} S &\to aA \mid bB \\ A &\to aA \mid B \mid \varepsilon \\ B &\to bB \mid \varepsilon \end{aligned}$$

Let us analyze the two production paths from the start symbol $S$:

• Case 1: Starting with $S \to aA$
  • $B$ generates any number of $b$'s (including zero): $B \Rightarrow b^*$.
  • $A$ generates $a^* B$ or $a^*$, which simplifies to $a^* b^*$.
  • Thus, $S \to aA \Rightarrow a(a^* b^*) = a^+ b^*$. This corresponds to strings $a^m b^n$ where $m > 0$ and $n \ge 0$.
• Case 2: Starting with $S \to bB$
  • $S \to bB \Rightarrow b(b^*) = b^+$. This corresponds to strings $a^m b^n$ where $m = 0$ and $n > 0$.

Combining both cases, the language $L(G_2)$ contains all strings of the form $a^m b^n$ except the empty string $\varepsilon$ (where $m=0$ and $n=0$). Therefore, at least one of $m$ or $n$ must be strictly greater than $0$:

$$L(G_2) = \{ a^m b^n \mid m > 0 \text{ or } n > 0 \}$$

Thus, the correct pair of languages is given in Option D.