# GATE Papers >> CSE >> 2016 >> Question No 52

Question No. 52

Consider the following context-free grammars:

$G_1:\;S\rightarrow aS\vert B,B\rightarrow b\vert bB$
$G_2:\;S\rightarrow aA\vert bB,A\rightarrow aA\vert B\vert\varepsilon,B\rightarrow bB\vert\varepsilon$

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

##### Answer : (D) $\{a^mb^n\vert m\geq0\;\mathrm{and}\;n>0\}\mathrm{and}\{a^mb^n\vert m>0\;\mathrm{or}\;n>0\}$

Solution of Question No 52 of GATE 2016 CSE Paper

$\begin{array}{l}{\boldsymbol G}_\mathbf1\boldsymbol:\boldsymbol\;\;\;\;\;\;\;\;\;\;\;\;S\rightarrow aS\vert B\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;B\rightarrow b\vert bB\\{\boldsymbol G}_\mathbf2\boldsymbol:\boldsymbol\;\;\;\;\;\;\;\;\;\;\;\;S\rightarrow aA\vert bB\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;A\rightarrow aA\vert B\vert\mathrm\varepsilon\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;B\rightarrow bB\vert\mathrm\varepsilon\\{\boldsymbol G}_\mathbf3\boldsymbol:\;\;\;\;\;\;\;\;\;\;\;\;B\rightarrow b\vert bB\Rightarrow B\rightarrow b^+\end{array}$

Now substitute in $S\rightarrow aS\vert B$

We get $S\rightarrow aS\vert b^+\Rightarrow S\rightarrow a\ast b^+$

So, $L\left(G_1\right)=\left\{a^mb^n\vert m\geq o\;\mathrm{and}\;n>0\right\}$

$G_2=B\rightarrow bB\vert\varepsilon\Rightarrow B\rightarrow b\ast$

Substitute in $A\rightarrow aA\vert B\vert\varepsilon\Rightarrow A\rightarrow aA\vert b\ast\vert\varepsilon$

$\begin{array}{l}\Rightarrow A\rightarrow aA\vert b\ast\\\Rightarrow A\rightarrow a\ast b\ast\end{array}$

Now substitute $A$ and $B$ in $\begin{array}{l}S\rightarrow aA\vert bB\\\end{array}$

$\Rightarrow S\rightarrow aa\ast\;b\ast\vert bb\ast$

$\Rightarrow S\rightarrow aa\ast\;b\ast+bb\ast$

So       $L\left(G_2\right)=\left\{a^mb^n\vert m>0\;\mathrm{or}\;n>0\right\}$

So correct answer is choice (d).