The GATE Grind

GATE 2016 CS – Question 52

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

Consider the following context-free grammars:

$G_1$: $S \rightarrow aS \mid B$, $B \rightarrow b \mid bB$

$G_2$: $S \rightarrow aA \mid bB$, $A \rightarrow aA \mid B \mid \epsilon$, $B \rightarrow bB \mid \epsilon$

Which one of the following pairs of languages is generated by $G_1$ and $G_2$, respectively?

  1. $\{a^m b^n \mid m > 0 \text{ or } n > 0\}$ and $\{a^m b^n \mid m > 0 \text{ and } n > 0\}$
  2. $\{a^m b^n \mid m > 0 \text{ and } n > 0\}$ and $\{a^m b^n \mid m > 0 \text{ or } n \geq 0\}$
  3. $\{a^m b^n \mid m \geq 0 \text{ or } n > 0\}$ and $\{a^m b^n \mid m > 0 \text{ and } n > 0\}$
  4. $\{a^m b^n \mid m \geq 0 \text{ and } n > 0\}$ and $\{a^m b^n \mid m > 0 \text{ or } n > 0\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\{a^m b^n \mid m \geq 0 \text{ and } n > 0\}$ and $\{a^m b^n \mid m > 0 \text{ or } n > 0\}$

Explanation

In $G_1$, $B$ produces one or more $b$'s, and $S$ adds any number of $a$'s in front, so it generates $a^m b^n$ with $m \geq 0$ and $n \geq 1$. In $G_2$, starting with $a$ gives $a$ followed by any number of $a$'s and then any number of $b$'s, which covers $a^m b^n$ with $m > 0$ and $n \geq 0$. Starting with $b$ gives one or more $b$'s, which covers $n > 0$ with $m = 0$. Together this is $a^m b^n$ with $m > 0$ or $n > 0$.