The GATE Grind

GATE 2017 CS (CS1) – 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

In both grammars $T$ generates $c^m$ and sits **between** the matching symbols:

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).

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →