GATE CSE 2025 | Set 1 | Question: 9

Question

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as:
$$ \begin{array}{l} S \rightarrow a a B \mid A b b \\ A \rightarrow a \mid a A \\ B \rightarrow b \mid b B \end{array}$$
Which ONE of the languages $L(G)$ is accepted by $G$ ?

• A. $L(G)=\left\{a^{2} b^{n} \mid n \geq 1\right\} \cup\left\{a^{n} b^{2} \mid n \geq 1\right\}$
• B. $L(G)=\left\{a^{n} b^{2 n} \mid n \geq 1\right\} \cup\left\{a^{2 n} b^{n} \mid n \geq 1\right\}$
• C. $L(G)=\left\{a^{n} b^{n} \mid n \geq 1\right\}$
• D. $L(G)=\left\{a^{2 n} b^{2 n} \mid n \geq 1\right\}$

Comments

Answer = A ,,, https://correctbrain.com/buy/

---

How the power can be same? Is the following expression correct, pls clarify anyone

---

 

So the trick here is start from deriving single single variable first, 

A  - a, aa, aaa, aaaa.....  means

                        

 

B  - b, bb, bbb, bbbb.....  means

                        

 

Now, Case 1 :  S → aaB

we can write as

                                 

                      

Now,  Case 2 :  S → Abb

we can write as 

                      

                     

 

Hence, Ans (A)

---

Bottom to Top
$a^2 b^{+} \cup a^{+} b^2 $                           
$\left\{a^2 b^n \mid n \geq 1\right\} \cup\left\{a^n b^2 \mid n \geq 1\right\}$

Answer 1

Option A:

Is aabbb ∈ L(G)?  S → aaB → aabbb 

Is aaabb ∈ L(G)?  S → Abb → aaA bb → aaabb 

Try a string like aab —  aab 

This matches exactly what the grammar produces.

---

Option B:

1. Try aabb ⇒ is this in option B?

   • aabb → 2 a’s, 2 b’s ⇒ doesn’t match either pattern (need a^2 b^1 or a^1 b^2) ❌
     So this contradicts, hence Option B ❌

---

Option C:

1.  aab ⇒ a²b ⇒ not equal number of a’s and b’s ❌

2.  abb ⇒ a¹b² ❌

3. aab — 2 a’s, 1 b ❌

Option D:

• aab — 2 a’s, 1 b ❌

• abb — 1 a, 2 b ❌

Does not include strings like aab, which are in grammar   

Answer 2

We are given a context-free grammar $G$:

• Variables: $S, A, B$
• Terminals: $a, b$
• Start symbol: $S$

Rules:
$$
\begin{aligned}
S &\to aaB \mid Abb \\
A &\to a \mid aA \\
B &\to b \mid bB
\end{aligned}
$$

Step 1: Strings generated by $A$

Since $A \to a \mid aA$, this produces one or more $a$'s:
$$
L(A) = { a^n \mid n \ge 1 }
$$

Step 2: Strings generated by $B$

Since $B \to b \mid bB$, this produces one or more $b$'s:
$$
L(B) = { b^n \mid n \ge 1 }
$$

Step 3: Strings generated by $S$

From $S \to aaB$:
$$
{ a^2 b^n \mid n \ge 1 }
$$

From $S \to Abb$:
$$
{ a^n b^2 \mid n \ge 1 }
$$

Step 4: Combine
$$
L(G) = { a^2 b^n \mid n \ge 1 } \cup { a^n b^2 \mid n \ge 1 }
$$

$$
\boxed{L(G) = { a^2 b^n \mid n \ge 1 } \cup { a^n b^2 \mid n \ge 1 }}
$$

 

Answer: Option A

Answer 3

 

Opt - A

Answer 4

Short Answer;-

Let's say the languages in the options 2, 3, and 4 as $L_2(G), L_3(G), L_4(G)$

String $aabbb \in L(G)$ but $aabbb \not\in $ $L_2(G), L_3(G), L_4(G)$.

so the answer is A.

Answer 5

$Answer: A$

Given CFG

$S \rightarrow aaB | Abb$

$A \rightarrow a | aA$

$B \rightarrow b | bB$

Lets go from bottom to top

$A \rightarrow a | aA  \implies$ generates strings like {a, aa, aaa, aaaa.....} $\implies a^+$

$B \rightarrow b | bB \implies$ generates strings like {b, bb, bbb, bbbb....} $\implies b^+$

$S \rightarrow aaB | Abb$

$ \implies$ $aab^+$ | $a^+bb$

$\implies$ $a^2b^+$ OR $a^+b^2$

$\implies$ ${a^2b^n OR  a^nb^2} \text{(where n$\geq$1)}$

$\text{so}  L(G) = {a^2b^n |n\geq1}$ $\cup$ ${a^nb^2 |n\geq1}$

Answer 6