GATE CSE 2026 Session 2 Q48: Constraints on a^i b^j c^k d^l that keep the language context-free

Let $\Sigma = \{a, b, c, d\}$ and let $L = \{a^i b^j c^k d^\ell \mid i, j, k, \ell \ge 0\}$ .

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

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, C, D (official GATE 2026 final answer key)

Concept used: A PDA can match counts that are properly nested; crossing dependencies need more than one stack.

First step: Check whether each pairing is nested (like $a$ with $d$ around $b$ with $c$ ) or crossing (like $a$ – $c$ and $b$ – $d$ ).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key