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

Question No. 52 CSE | GATE 2016

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).

Comments
No Comments
Leave a comment