GATE CS 2026 Set 2 — Question 48

We analyze each constraint:(A) $i + k = j + \ell \iff i - j = \ell - k$. This language is Context-Free. It can be generated by the union of two CFLs (one for $i \ge j$ and one for $i < j$). Alternatively, a PDA can push for $a$, pop for $b$ (switching to a 'negative' stack symbol if empty), then handle $c$ and $d$ to balance the count to 0.(B) $i = k$ and $j = \ell$. This generates $a^n b^m c^n d^m$. This involves crossing dependencies ($a$ matches $c$, $b$ matches $d$) and is a classic example of a non-Context-Free language.(C) $i = \ell$ and $j = k$. This generates $a^n b^m c^m d^n$. This involves nested dependencies ($a$ matches $d$, $b$ matches $c$). This is a standard Context-Free language (generated by $S \to aSd \mid B, B \to bBc \mid \epsilon$).(D) $i + j = k + \ell$. This requires the total number of $a$'s and $b$'s to equal the total number of $c$'s and $d$'s. Since all $a, b$ appear before $c, d$, a PDA can simply push a token for every $a$ and $b$, and then pop a token for every $c$ and $d$. If the stack is empty at the end, the string is accepted. Thus, it is Context-Free.Therefore, options (A), (C), and (D) ensure the language is Context-Free.