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: $m+p=n+q$.** Rewrite as $m-n=q-p$. After reading $a^mb^n$ the PDA keeps $|m-n|$ on the stack (and remembers the sign in its state). While reading $c^p$ it adjusts the counter, and while reading $d^q$ it must cancel exactly what is left. One counter is enough, so I is **context-free**.

**Language II: $m=n$ and $p=q$.** This is $\{a^nb^n\}\cdot\{c^pd^p\}$, a concatenation of two context-free languages. **Context-free.**

**Language III: $m=n=p$ and $p\ne q$.** The three blocks $a^m,b^n,c^p$ must all have equal length, which needs two comparisons at once (like $\{a^nb^nc^n\}$). **Not context-free** (pumping lemma).

**Language IV: $mn=p+q$.** Checking that the number of $c$'s plus $d$'s equals the **product** of two unbounded counts is multiplication, which a PDA cannot do. **Not context-free.**

So I and II only: option (B).

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →