Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thank you. I wonder what is wlog? Are you implying it is context free ^_^? –  Chan Aug 15 '11 at 23:39
1  
wlog = Without loss of generality. –  Yuval Filmus Aug 16 '11 at 20:38
    
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
    
This might be my personal taste, but I do not like the use of “wlog” (or “without loss of generality” for that matter) here. –  Tsuyoshi Ito Aug 17 '11 at 12:29
1  
@Chan: Hint: Is $x^ny^n$ context-free? –  Yuval Filmus Aug 18 '11 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.