GATE CS 2026 Set 2 Q38 — Regular and Context-free Languages

To determine which constraints ensure that $L = \{a^{i} b^{j} c^{k} d^{\ell} \mid i, j, k, \ell \geq 0\}$ is a context-free language (CFL), we analyze the dependencies between the symbol counts:

• Option A ($i+k=j+\ell$): This relation can be rewritten as $i - j = \ell - k$. We can construct a Pushdown Automaton (PDA) using a single stack to keep track of the difference. Alternatively, we can partition this into two context-free cases: $i \ge j$ (which yields strings of the form $a^m a^j b^j c^k d^k d^m$) and $i < j$ (yielding $a^i b^i b^m c^m c^\ell d^\ell$). Both cases are context-free, so their union is also a CFL.
• Option B ($i=k$ and $j=\ell$): This requires matching $a$'s with $c$'s, and $b$'s with $d$'s. These are cross-serial dependencies ($a \leftrightarrow c$ and $b \leftrightarrow d$). A PDA cannot handle overlapping matches, making this language non-context-free.
• Option C ($i=\ell$ and $j=k$): This requires matching the outermost symbols ($a$ with $d$) and the innermost symbols ($b$ with $c$). These are nested dependencies, which perfectly match the LIFO structure of a stack. The language is generated by the CFG: $$S \to a S d \mid T$$ $$T \to b T c \mid \epsilon$$ Thus, it is a CFL.
• Option D ($i+j=k+\ell$): Here, the total number of prefix symbols ($a$ and $b$) must equal the total number of suffix symbols ($c$ and $d$). A PDA can simply push all $a$'s and $b$'s onto the stack, and then pop one symbol for each incoming $c$ and $d$. Since a PDA can accept this language, it is a CFL.