3
$\begingroup$

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.

  • 0
    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?2011-08-22

1 Answers 1

2

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. $

  • 0
    I can construct automat with stack which recognizes this language2019-03-24