Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language?
My initial thought was to prove that it is not a CFL by using Pumping Lemma for CFG with the string $s = a^pb^pc^pd^p$. Since $|s| = 4p > p$, and $s \in L$, so I can divide it into $s = uvxyz$, where $|vy| \geq 1, |vxy| \leq p$. Then I check for all the possibilities of $|vxy|$ in $s$:
- $vxy = a^e$
- $vxy = a^eb^f$
- $vxy = b^ec^f$
The other two cases: $c^ed^f, d^e$ would be the same as the first two cases because the symmetric property. By pumping up $s$, I can see that $s_i \not\in L$.
On the other hand, I've just learned pumping lemma for CFG, I couldn't convince myself this language is not context free. I wonder if anyone could give me a hint to this problem. Thank you.
Best Answer
Hint: Suppose wlog that $i \geq l$. Then $$ a^i b^j c^k d^l = a^{l+(i-l)} b^{(i-l)+k} c^k d^l. $$