# Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language?

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.

-
Have you thought that the language might be context-free? If you cannot prove that it is not for a while, the next thing to do naturally is to try to prove that it is context-free. –  Tsuyoshi Ito Aug 17 '11 at 12:26
A language is context-free if and only if there is a push-down automaton accepting it. The criterion for acceptance is equivalent to i - j + k - l = 0. Can a push-down automaton verify that this sum is equal to 0? –  Tanner Swett Aug 22 '11 at 1:36

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.$$
Thank you. I wonder what is wlog? Are you implying it is context free ^_^? –  Chan Aug 15 '11 at 23:39
Is it CFL? since I already found the case that no matter how I pump (up or down), it's still in $L$. –  Chan Aug 17 '11 at 8:05
@Chan: Hint: Is $x^ny^n$ context-free? –  Yuval Filmus Aug 18 '11 at 17:24