The GATE Grind

GATE 2018 CS – Question 45

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

Consider the following languages:

I. $\{a^mb^nc^pd^q\mid m+p=n+q,\ \text{where }m,n,p,q\ge0\}$

II. $\{a^mb^nc^pd^q\mid m=n\text{ and }p=q,\ \text{where }m,n,p,q\ge0\}$

III. $\{a^mb^nc^pd^q\mid m=n=p\text{ and }p\ne q,\ \text{where }m,n,p,q\ge0\}$

IV. $\{a^mb^nc^pd^q\mid mn=p+q,\ \text{where }m,n,p,q\ge0\}$

Which of the languages above are context-free?

  1. I and IV only
  2. I and II only
  3. II and III only
  4. II and IV only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) I and II only

Explanation

Language I can be recognised with a single counter ($a$ and $c$ push, $b$ and $d$ pop), and II is $a^nb^n\cdot c^pd^p$, which is context-free. III needs $m=n=p$ checked together, which is not context-free, and IV needs multiplication $mn$, which is not context-free either. So only I and II are.