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
SdNDKB http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 13:22:01  by  dobsonz
Oy6u8e https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

Posted on  03/12/2020 23:22:09  by  dobson
b4Cq2g http://xnxx.in.net/ xnxx videos

Posted on  12/12/2020 20:23:33  by  johnan
RZH3cw https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 05:59:22  by  dobson
hehTbg https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 06:59:16  by  dobson
whX7D2 https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 08:42:10  by  dobson
4HOssc http://waldorfdollshop.us/ waldorf doll

Posted on  09/01/2021 12:56:29  by  johnanz
Leave a comment