Question

Consider the following context-free grammars:
$G_1:S\to aS|B,B\to b|bB$
$G_2:S\to aA|bB,A\to aA|B|\epsilon ,B\to bB|\epsilon$
$Whichoneofthefollowingpairsoflanguagesisgeneratedby{G}_{1}and{G}_2,respectively?$

• A. $\{a^m{b}^n|m>0andn>0\}and\{a^m{b}^n|m>0orn\ge 0\}$
• B. $\{a^m{b}^n|m\ge 0andn>0\}and\{a^m{b}^n|m>0orn>0\}$
• C. $\{a^m{b}^n|m>0orn>0\}and\{a^m{b}^n|m>0andn>0\}$
• D. $\{a^m{b}^n|m\ge 0orn>0\}and\{a^m{b}^n|m>0andn>0\}$

Answer 1

The correct option is B $\{a^m{b}^n|m\ge 0andn>0\}and\{a^m{b}^n|m>0orn>0\}$

$G_1:S\to aS|B$
$B\to b|bB$
$G_2:S\to aA|bB$
$A\to aA|B|\epsilon$
$B\to bB|\epsilon$
$G:B\to b|bB\Rightarrow B\to b^{+}$
$NowsubstituteinS\to aS|B$
$WegetS\to aS|b^{+}\Rightarrow S\to a^{\ast }{b}^{+}$
$So,L\left(G_1\right)=\{a^m{b}^n|m\ge 0andn>0\}$
$G_2=B\to bB|\epsilon \Rightarrow B\to b^{\ast }$
Substitute in A $\to aA|B|\epsilon \Rightarrow A\to aA|b^{\ast }|\epsilon$
$\Rightarrow A\to aA|b^{\ast }$
$\Rightarrow A\to a^{\ast }{b}^{\ast }$
$NowsubstituteAandBinS\to aA|bB$
$\Rightarrow S\to a{a}^{\ast }{b}^{\ast }|b{b}^{\ast }$
$S\to a{a}^{\ast }{b}^{\ast }+b{b}^{\ast }$
$So,L\left(G_2\right)=\{a^m{b}^n|m>0orn>0\}$
So correct answer is choice (d).