GATE CS 2017 Set 1 — Question 37

Let's analyze the languages generated by $G_1$ and $G_2$.For $G_1$:
$S \to aSb \mid T$
$T \to cT \mid \epsilon$
$T$ generates any number of $c$'s, i.e., $c^*$.
$S$ generates $a^n T b^n$, which results in $a^n c^m b^n$ where $n, m \ge 0$.
So, $L(G_1) = \{ a^n c^m b^n \mid n, m \ge 0 \}$.For $G_2$:
$S \to bSa \mid T$
$T \to cT \mid \epsilon$
$T$ generates $c^*$.
$S$ generates $b^k T a^k$, which results in $b^k c^p a^k$ where $k, p \ge 0$.
So, $L(G_2) = \{ b^k c^p a^k \mid k, p \ge 0 \}$.Now consider the intersection $L(G_1) \cap L(G_2)$. A string $w$ must belong to both languages.
From $L(G_1)$, $w$ must be of the form $a^n c^m b^n$.
From $L(G_2)$, $w$ must be of the form $b^k c^p a^k$.Case 1: If $n > 0$, $w$ starts with $a$. However, strings in $L(G_2)$ start with $b$ (if $k>0$) or $c$ (if $k=0$). Thus, a string starting with $a$ cannot be in $L(G_2)$. So, $n$ must be 0.
Case 2: If $k > 0$, $w$ starts with $b$. However, strings in $L(G_1)$ start with $a$ (if $n>0$) or $c$ (if $n=0$). Thus, a string starting with $b$ cannot be in $L(G_1)$. So, $k$ must be 0.Therefore, for a string to be in the intersection, we must have $n=0$ and $k=0$.
If $n=0$, $w \in L(G_1)$ becomes $c^m$.
If $k=0$, $w \in L(G_2)$ becomes $c^p$.The intersection consists of strings consisting only of $c$'s. i.e., $L(G_1) \cap L(G_2) = \{ c^m \mid m \ge 0 \} = c^*$.This language $c^*$ is a regular language. Since there is no upper bound on $m$, it is an infinite language.
Thus, the language is not finite but regular.