GATE 2017 CS (CS1) – Question 47
Consider the context-free grammars over the alphabet $\{a, b, c\}$ given below. $S$ and $T$ are non-terminals.
$G_1: S \rightarrow aSb \mid T, \quad T \rightarrow cT \mid \epsilon$
$G_2: S \rightarrow bSa \mid T, \quad T \rightarrow cT \mid \epsilon$
The language $L(G_1) \cap L(G_2)$ is
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) Not finite but regular.
Explanation
In both grammars $T$ generates $c^m$ and sits **between** the matching symbols:
- $G_1$: $S\to aSb\mid T$ generates $a^nc^mb^n$.
- $G_2$: $S\to bSa\mid T$ generates $b^kc^la^k$.
A string in both languages must have the form $a^nc^mb^n$ and also $b^kc^la^k$. If it contained any $a$ or $b$, the first form starts with $a$ but the second starts with $b$, which is impossible. So $n=k=0$ and the strings are just $c^m$.
$$L(G_1)\cap L(G_2)=\{c^m\mid m\ge0\}=c^*,$$
which is infinite and regular. Option (B).