GATE 2026 CS2 Q.48: solution and answer

GATE 2026 · CS2Q.48 · 2 marks · MSQ

Let $Σ = {a, b, c, d}$ and let $L = {a^{i} b^{j} c^{k} d^{ℓ} ∣ i, j, k, ℓ \geq 0}$ .

Which of the following constraints ensure(s) that the language $L$ is context-free?

(A)
$i + k = j + ℓ$
(B)
$i = k$ and $j = ℓ$
(C)
$i = ℓ$ and $j = k$
(D)
$i + j = k + ℓ$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Options (A), (C) and (D) make $L$ context-free. Only (B), ${a^{i} b^{j} c^{i} d^{j}}$ , is not context-free.

Official answer: A, C, DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Each option adds one constraint to $L = {a^{i} b^{j} c^{k} d^{ℓ} ∣ i, j, k, ℓ \geq 0}$ . Check each restricted language for context-freeness separately.
(A) $i + k = j + ℓ$ . Split on whether $i \geq j$ . If $i = j + m$ with $m \geq 0$ , then $j + m + k = j + ℓ$ gives $ℓ = k + m$ , so the word is $a^{m} (a^{j} b^{j}) (c^{k} d^{k}) d^{m}$ . If $j = i + m$ with $m > 0$ , then $i + k = i + m + ℓ$ gives $k = ℓ + m$ , so the word is $(a^{i} b^{i}) (b^{m} c^{m}) (c^{ℓ} d^{ℓ})$ .
Both cases have context-free grammars. First case: $S_{1} \to a S_{1} d ∣ X Y$ , $X \to a X b ∣ ε$ , $Y \to c Y d ∣ ε$ , which gives exactly $a^{m} a^{j} b^{j} c^{k} d^{k} d^{m}$ . Second case: $S_{2} \to X Z Y$ with the same $X$ and $Y$ and $Z \to b Z c ∣ ε$ . With $S \to S_{1} ∣ S_{2}$ the grammar generates the whole language (check: $a d$ , $b c$ , $ab c d$ are generated; $a c$ has $i + k = 2 \neq = 0 = j + ℓ$ and is not). So (A) is context-free.
(B) $i = k$ and $j = ℓ$ , i.e. ${a^{i} b^{j} c^{i} d^{j}}$ : the $a$ 's are matched with the $c$ 's and the $b$ 's with the $d$ 's, so the two dependencies cross. Pumping lemma: take $w = a^{n} b^{n} c^{n} d^{n}$ , where $n$ is the pumping length. Any split $w = uv x y z$ with $∣ v x y ∣ \leq n$ and $∣ v y ∣ \geq 1$ puts $v x y$ inside at most two neighbouring blocks. If $v$ or $y$ holds two different letters, pumping up breaks the order $a^{*} b^{*} c^{*} d^{*}$ . Otherwise pumping changes the count of $a$ or $b$ (but not $c$ or $d$ ), or of $b$ or $c$ , or of $c$ or $d$ . In every case some pair $(a, c)$ or $(b, d)$ loses its balance, so $u v^{2} x y^{2} z \in / L$ . (B) is not context-free.
(C) $i = ℓ$ and $j = k$ , i.e. ${a^{i} b^{j} c^{j} d^{i}}$ : the dependencies are nested. $S \to a S d ∣ T$ , $T \to b T c ∣ ε$ generates exactly this language, so (C) is context-free.
(D) $i + j = k + ℓ$ . Split on whether $i \geq ℓ$ . If $i = ℓ + m$ with $m \geq 0$ , then $ℓ + m + j = k + ℓ$ gives $k = j + m$ , so the word is $a^{ℓ} a^{m} (b^{j} c^{j}) c^{m} d^{ℓ}$ . If $ℓ = i + m$ with $m > 0$ , then $i + j = k + i + m$ gives $j = k + m$ , so the word is $a^{i} b^{m} (b^{k} c^{k}) d^{m} d^{i}$ .
Both cases are nested, so one grammar covers them: $S T U V W \to a S d ∣ T ∣ V \to a T c ∣ U \to b U c ∣ ε \to bV d ∣ W \to bW c ∣ ε$ $S \to a S d ∣ T$ gives $a^{ℓ} T d^{ℓ}$ , then $T$ gives $a^{m} b^{j} c^{j} c^{m}$ , the first case. $S \to a S d ∣ V$ gives $a^{i} V d^{i}$ , then $V$ gives $b^{m} b^{k} c^{k} d^{m}$ , the second case. Check on short strings: $a c$ ( $S \Rightarrow T \Rightarrow a T c \Rightarrow a c$ ), $b d$ , $a d$ and $ab c d$ are generated; $ab$ has $i + j = 2 \neq = 0$ and is not. A PDA sees it too: push one symbol for every $a$ and $b$ , pop one for every $c$ and $d$ , let the finite control enforce the order $a^{*} b^{*} c^{*} d^{*}$ , and accept on an empty stack. So (D) is context-free.
Correct options: (A), (C) and (D).

KEY IDEA

A one-stack machine can check a constraint when the matched counts are nested: the symbols counted first are matched in reverse order by the symbols counted last. In (D), every $a$ and $b$ is pushed and every $c$ and $d$ pops, so the constraint is a single stack balance. In (A) and (C) the constraint splits into a union of nested patterns. (B) needs two crossing matches ( $a$ with $c$ and $b$ with $d$ ), and a single stack cannot do both.

WATCH OUT FOR

Calling (D) non-context-free because it involves all four letters. $i + j = k + ℓ$ is one count balanced against another, the shape of ${x^{n} y^{n}}$ with $x \in {a, b}$ and $y \in {c, d}$ , and a PDA checks it with one stack. An Ogden or pumping argument against (D) breaks down because the pumped window can be a block of $a$ 's together with a block of $d$ 's, with all the $b$ 's and $c$ 's between them, and pumping both blocks keeps the sums equal. Another slip is putting the inner nonterminal in the wrong place in a grammar for (A), for example $X \to a X b ∣ Y$ with $Y \to c Y d$ , which produces $a^{j} c^{k} d^{k} b^{j}$ instead of $a^{j} b^{j} c^{k} d^{k}$ .

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 8 Context-free languages questions, with notes

GATE 2026 CS2 Q.48: solution and answer

Answer and solution

More Context-free languages questions