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
    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.2011-08-17
  • 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
    Thank you. I wonder what is `wlog`? Are you implying it is context free ^_^?2011-08-15
  • 1
    wlog = Without loss of generality.2011-08-16
  • 0
    Is it CFL? since I already found the case that no matter how I pump (up or down), it's still in $L$.2011-08-17
  • 0
    This might be my personal taste, but I do not like the use of “wlog” (or “without loss of generality” for that matter) here.2011-08-17
  • 0
    @Chan: You should think about the hint.2011-08-17
  • 0
    @Yuval Filmus: I thought about it from yesterday until today. Still didn't see anything :(, could you give an extra hint? Thank you.2011-08-18
  • 1
    @Chan: Hint: Is $x^ny^n$ context-free?2011-08-18
  • 0
    So $L$ is context-free ?2015-05-05
  • 0
    @user220688 What do you think?2015-05-05
  • 0
    I can construct automat with stack which recognizes this language2015-05-05