GATE 2023 CS Q.39: solution and answer

Official answer: BSource: Official answer key, GATE 2023 CS (IIT Kanpur)

1. Solve the inner non-terminal first. In $X\to aX\mid Xb\mid a\mid b$, each use of $X\to aX$ puts an $a$ on the left and each use of $X\to Xb$ puts a $b$ on the right. The derivation stops with exactly one terminal $c\in \{a,b\}$ from $X\to a$ or $X\to b$. So $L(X)=a^{\ast }(a+b)b^{\ast }$, that is, strings $a^{i}c{b}^j$ with $i,j\ge 0$ and $c\in \{a,b\}$.

2. $S\to aSb$ wraps $n\ge 0$ matching pairs around $X$, and $S\to X$ ends the wrapping. So $L(G)=\{a^{n}w{b}^n\mid n\ge 0,w\in a^{\ast }(a+b)b^{\ast }\}$.

3. Write $w=a^{i}c{b}^j$. Then the string is $a^{n+i}c{b}^{j+n}$, which has the form $a^{m}c{b}^k$ with $m,k\ge 0$. So $L(G)\subseteq a^{\ast }(a+b)b^{\ast }$.

4. Conversely, any string $a^{m}c{b}^k$ in $a^{\ast }(a+b)b^{\ast }$ is generated by taking $n=0$, $i=m$, $j=k$, since $S\to X$ already gives all of $L(X)$. So $L(G)=a^{\ast }(a+b)b^{\ast }$, which is regular, and (B) is correct.

5. Check the others. (A): $ba\in (a+b{)}^{\ast }$, but $ba\notin L(G)$, because in $a^{\ast }(a+b)b^{\ast }$ every symbol after the single special symbol $c$ is a $b$, and a string starting with $b$ must have $c$ as that first $b$, leaving only $b$'s after it. So (A) is false. (C): $bba\in a^{\ast }{b}^{\ast }(a+b)$ by taking $a^0{b}^{2}a$, but $bba\notin L(G)$. The only symbols before $c$ are $a$'s, so $c$ would be the first $b$ with only $b$'s after it, or the last $a$ with only $a$'s before it, and neither fits $bba$. So (C) is false. (D): $L(G)$ is regular, so (D) is false.