3 3 votes Consider the following context-free grammars:$$\begin{aligned}& G_1: S \rightarrow a S|S b| \epsilon \\& G_2: S \rightarrow a S b|a A, A \rightarrow a A| \epsilon\end{aligned}$$Which one of the following pairs of languages is generated by $G_1$ and $G_2$, respectively? $\left\{a^m b^n \mid m \geq 0, n \geq 0\right\}$ and $\left\{a^m b^n \mid m=n\right\}$ $\left\{a^m b^n \mid m \geq 0, n \geq 0\right\}$ and $\left\{a^m b^n \mid m \geq n, m>0\right\}$ $\left\{a^m b^n \mid m>0, n \geq 0\right\}$ and $\left\{a^m b^n \mid m \geq n\right\}$ $\left\{a^m b^n \mid m \geq 0, n \geq 0\right\}$ and $\left\{a^m b^n \mid m>n\right\}$ Theory of Computation goclasses theory-of-computation goclasses-cs-dpp goclasses-cs-dpp-day-135 goclasses-toc-practice-questions + – GO Classes 368 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
1 1 vote The correct choice is D.For $G_1$ : using $a S$ you can generate any number of leading a's, and using $S b$ any number of trailing b's; with $\epsilon$ you can stop - so $G_1$ generates all $a^m b^n$ with $m, n \geq 0$.For $G_2$ : every use of $a S b$ pairs one a with one b , and the $a A$ branch supplies extra a's (at least one a overall because of the leading $a$ in $a A$ ), so strings satisfy $m>n$. GO Classes answered Nov 18, 2025 • edited Nov 20, 2025 by GO Classes GO Classes comment Share Follow See all 2 Comments 2 2 Comments reply VISION_GATE commented Nov 18, 2025 reply Follow flag ans will be d pls correct it 2 2 replyShare Vinayagam S commented Nov 18, 2025 reply Follow flag Yes 0 0 replyShare Please log in or register to add a comment.
0 0 votes Correct options is DFor G1 Language L = (a+b)^* and for G2 Language = a^na^+b^n which is equal to L= a^mb^n where m>n Vivid_Vivek answered Jun 4 Vivid_Vivek comment Share Follow 0 reply Please log in or register to add a comment.
