GATE 2018 CS Q.35: solution and answer

Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)

1. Language I: $m+p=n+q$ is the same as $m-n=q-p$. Split on the sign of this common value $k$.

2. Case $m\ge n$: put $k=m-n=q-p\ge 0$. Then $m=n+k$ and $q=p+k$, so the word is $a^k(a^n{b}^n)(c^p{d}^p)d^k$. A grammar is $S_1\to a{S}_{1}d\mid X$, $X\to AB$, $A\to aAb\mid \epsilon$, $B\to cBd\mid \epsilon$. This case is context-free.

3. Case $m<n$: put $k=n-m=p-q>0$. Then $n=m+k$ and $p=q+k$, so the word is $(a^m{b}^m)(b^k{c}^k)(c^q{d}^q)$, a concatenation of three languages of the form $x^i{y}^i$. This case is context-free.

4. The union of two context-free languages is context-free, so I is context-free.

5. Language II: $a^n{b}^n{c}^p{d}^p$ is generated by $S\to AB$, $A\to aAb\mid \epsilon$, $B\to cBd\mid \epsilon$. So II is context-free.

6. Language III $=\{a^n{b}^n{c}^n{d}^q\mid q\ne n\}$ is not context-free. Use Ogden's lemma with constant $N$. Take $z=a^N{b}^N{c}^N{d}^{2N}$, which is in III because $2N\ne N$. Mark the $N$ letters $a$. Write $z=uvwxy$ with $vx$ containing a marked letter and $vwx$ containing at most $N$ marked letters.

7. If $v$ or $x$ contains two different letters, then $u{v}^{2}w{x}^{2}y$ is not of the form $a^{\ast }{b}^{\ast }{c}^{\ast }{d}^{\ast }$, so it is outside III. Otherwise $v$ and $x$ each repeat one letter, and since $a$ is the first block, $vx$ contains at least one $a$. Then $v$ and $x$ together repeat at most one letter other than $a$, so at least one of the counts of $b$ and $c$ is unchanged and equals $N$. In $u{v}^{2}w{x}^{2}y$ the number of $a$'s is greater than $N$, so $m=n=p$ fails and the word is not in III. This holds for every split, so III is not context-free.

8. Language IV $=\{a^m{b}^n{c}^p{d}^q\mid mn=p+q\}$ is not context-free. Use Ogden's lemma. Take $z=a^N{b}^N{c}^{N^2}$, which is in IV because $N\cdot N=N^2+0$. Mark every $b$ and every $c$. Then $vwx$ has at most $N$ marked letters and $vx$ has at least one.

9. If $vwx$ contained an $a$ and a $c$, it would contain all $N$ letters $b$ plus a $c$, which is $N+1$ marked letters, impossible. So $vwx$ lies inside $a^{\ast }{b}^{\ast }$ or inside $b^{\ast }{c}^{\ast }$. Again a letter-mixing $v$ or $x$ gives a word outside the form $a^{\ast }{b}^{\ast }{c}^{\ast }{d}^{\ast }$.

10. Now pump with $i=2$ and let $v$, $x$ repeat $j$ and $k$ letters. (a) $v=a^j$, $x=b^k$ with $k\ge 1$: the word has $m=N+j$, $n=N+k$, $p=N^2$, and $mn>N^2=p+q$. (b) $v$, $x$ both inside the $b$'s: $n$ grows, $m$ and $p$ stay, so $mn>p$. (c) both inside the $c$'s: $p$ grows only, so $p+q>mn$. (d) $v=b^j$, $x=c^k$ with $j+k\ge 1$: here $mn=N(N+j)$ and $p=N^2+k$, so equality needs $k=Nj$. If $j\ge 1$ then $vx$ holds $j+Nj>N$ marked letters, which is not allowed. If $j=0$ then $k=0$, but $vx$ must contain a marked letter. So equality fails. In every case $u{v}^{2}w{x}^{2}y\notin$ IV, so IV is not context-free.

11. Hence exactly I and II are context-free, which is option (B).