The GATE Grind

GATE 2017 CS – Question 47

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

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

  1. Finite.
  2. Not finite but regular.
  3. Context-Free but not regular.
  4. Recursive but not context-free.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Not finite but regular.

Explanation

$L(G_1) = \{a^n b^n c^m\}$ and $L(G_2) = \{b^k a^k c^l\}$. A string in both must start with $a$'s followed by $b$'s and also start with $b$'s followed by $a$'s, which is only possible when there are no $a$'s or $b$'s. The intersection is $\{c^m \mid m \geq 0\}$, which is infinite and regular.