GATE CS 2017 Set 1 Q.37 (CS Q.37): Context-Free Grammars, Pushdown Automata and CFLs

Consider the context-free grammars over the alphabet $\{a, b, c\}$ given below. $S$ and $T$ are non-terminals.

G_1: S \to a S b \mid T, \quad T \to c T \mid \epsilon

G_2: S \to b S a \mid T, \quad T \to c T \mid \epsilon

The language $L(G_1) \cap L(G_2)$ is

Finite.

Not finite but regular.

Context-Free but not regular.

Recursive but not context-free.

Official answer and solution

Solution

Find the languages generated by grammars $G_1$ and $G_2$ , compute their set intersection, and classify the resulting language.

Grammar $G_1$ has productions:

S \to a S b \mid T, \quad T \to c T \mid \epsilon

Here $T$ generates any string in $c^*$ , and each application of $S \to a S b$ adds matched $a$ 's and $b$ 's. Thus:

L(G_1) = \{a^n c^m b^n \mid n \ge 0, m \ge 0\}

Grammar $G_2$ has productions:

S \to b S a \mid T, \quad T \to c T \mid \epsilon

Similarly, $T$ generates $c^*$ , and each application of $S \to b S a$ adds matched $b$ 's at the beginning and $a$ 's at the end. Thus:

L(G_2) = \{b^k c^m a^k \mid k \ge 0, m \ge 0\}

Now consider the intersection $L = L(G_1) \cap L(G_2)$ :

If $n > 0$ , any string in $L(G_1)$ starts with 'a'. But any string in $L(G_2)$ with $k > 0$ starts with 'b'.
If $n = 0$ , strings in $L(G_1)$ are purely of the form $c^m$ .
If $k = 0$ , strings in $L(G_2)$ are purely of the form $c^m$ .

Therefore, the only strings common to both languages are those with $n = 0$ and $k = 0$ :

L(G_1) \cap L(G_2) = \{c^m \mid m \ge 0\} = c^*

The language $c^*$ is infinite and regular (recognized by a single-state DFA with a loop on $c$ ). Hence, the intersection is not finite but regular.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.