GATE CS 2017 Set 1 Q37 — Context-free Grammars and Push-down Automata

To find the language $L(G_1) \cap L(G_2)$, let us first determine the languages generated by the individual grammars $G_1$ and $G_2$.

1. Analyzing Grammar $G_1$

The productions are:

The non-terminal $T$ generates any number of $c$'s, i.e., $L(T) = c^*$.

The non-terminal $S$ recursively wraps $T$ with an equal number of $a$'s on the left and $b$'s on the right. Thus:

2. Analyzing Grammar $G_2$

The productions are:

Similarly, $T$ generates $c^*$, and $S$ wraps it with an equal number of $b$'s on the left and $a$'s on the right. Thus:

3. Finding the Intersection $L(G_1) \cap L(G_2)$

Let $w \in L(G_1) \cap L(G_2)$. Then $w$ must satisfy the formats of both languages simultaneously:

• Case 1: $n > 0$
  If $n > 0$, the string $w$ starts with the symbol $a$. For $w$ to also belong to $L(G_2)$, the string $b^k c^j a^k$ must start with $a$. This is only possible if $k = 0$ (so it doesn't start with $b$) and $j > 0$ with the first symbol being $a$, which is impossible because $c^j$ contains only $c$'s. Thus, no string with $n > 0$ can belong to the intersection.
• Case 2: $n = 0$
  If $n = 0$, then $w = c^m$. For this to match $b^k c^j a^k$, we must have $k = 0$, which gives $w = c^j$. This is perfectly consistent for any $m = j \ge 0$.

Therefore, the intersection contains only strings of the form $c^m$ for $m \ge 0$:

Conclusion

The language $c^*$ is infinite and can be represented by a regular expression, meaning it is regular. Thus, the language is not finite but regular.