The GATE Grind

GATE 2026 CS (CS2) – Question 48

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple select

Let $\Sigma=\{a,b,c,d\}$ and let $L=\{a^i b^j c^k d^l \mid i,j,k,l \ge 0\}$. Which of the following constraints ensure(s) that the language is context-free?

  1. $i+k=j+l$
  2. $i=k$ and $j=l$
  3. $i=l$ and $j=k$
  4. $i+j=k+l$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $i+k=j+l$; (C) $i=l$ and $j=k$; (D) $i+j=k+l$

Explanation

Option (A) is context-free because the constraint $i+k=j+l$ can be enforced by a single counter that increases on $a$, decreases on $b$, increases on $c$, and decreases on $d$. Option (C) is context-free because it imposes the nested matching pattern $a^i b^j c^j d^i$. Option (D) is also context-free because the single counter can increase through the $a$ and $b$ blocks and decrease through the $c$ and $d$ blocks. However, option (B) requires the crossing dependencies $a^i b^j c^i d^j$, which is not context-free. Therefore, the correct choices are (A), (C), and (D).