GATE 2018 CS – Question 45
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?
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).