Question 48

Reading $a^i b^j c^k d^\ell$ in order:

• (A) $i + k = j + \ell \iff i - j = \ell - k$: A PDA can push $a$'s, pop against $b$'s (maintaining $|i - j|$ with a sign symbol), then push/pop $c$'s and match against $d$'s. Thus $L$ is context-free.
• (B) $i = k$ and $j = \ell$: This imposes crossing dependencies ($a^i$ with $c^k$, and $b^j$ with $d^\ell$). By the pumping lemma for CFLs, $\{a^i b^j c^i d^j\}$ is not context-free.
• (C) $i = \ell$ and $j = k$: These are nested dependencies ($S \rightarrow aSd \mid T$, $T \rightarrow bTc \mid \epsilon$). A PDA pushes $i$ $a$'s, then pushes $j$ $b$'s, pops the $j$ $b$'s on reading $c^k$, and finally pops the $i$ $a$'s on reading $d^\ell$. Thus $L$ is context-free.
• (D) $i + j = k + \ell$: A PDA simply pushes one symbol for each $a$ and each $b$ ($i + j$ symbols total), and pops one symbol for each $c$ and each $d$ ($k + \ell$ symbols total). Thus $L$ is context-free.