Is the following language context free?
L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0}
I've tried to come up with a context free grammar to generate this but I can not, so I'm assuming its not context free. As for my proof through contradiction:
Assume that L is context free,
Let p be the constant given by the pumping lemma,
Choose string S = a^p b^p c^p d^p where S = uvwxy
As |vwx| <= p, then at most vwx can contain two distinct symbols:
case a) vwx contains only a single type of symbol, therefore uv^2wx^2y will result in i+s != k+r
case b) vwx contains two types of symbols:
i) vwx is composed of b's and c's, therefore uv^2wx^2y will result in i+s != k+r
Now my problem is that if vwx is composed of either a's and b's, or c's and d's, then pumping them won't necessary break the language as i and k or s and r could increase in unison resulting in i+s == k+r.
Am I doing something wrong or is this a context free language?
I can't come up with a CFG to generate that particular language at the top of my head either, but we know that a language is context free iff some pushdown automata recognizes it.
Designing such a PDA won't be too difficult. Some ideas to get you started: we know i+s=k+r. Equivalently, i-k-r+s = 0 (I wrote it in that order since that is the order in they appear). The crux of the problem is deciding what to do with the stack if (k+r)>i.
If you aren't familiar with PDA's or cannot use them to answer the problem, at least you know now that it is Context Free.
Good luck!