# CFG problem solved with PDA - looking for alternative solution

I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$ and what I have done so far is to make PDA which simply does the following:

• If on the stream there is "a" -> push $$\xi$$ in the stack

• If on the stream there is "b" and the stack is empty -> push $$\zeta$$ in the stack

• If on the stream there is "b" and there is $$\xi$$ in the stack then while there are $$\xi$$ in the stack read b from the stream and pop $$\xi$$.

• If there is "b" on the stream and no $$\xi$$ left in the stack continue reading "b" and push $$\zeta$$.

And so on counting the a,b,c and d's which I get, but the problem is that my transition function is getting really big and I'm gonna have some troubles to convert it into CFG, so there must be straightforward way to do it and seems I can't find it.

• "i'm gonna have some troubles to convert it into CFG," -- why? Big isn't necessarily hard, only tedious. "so there must be straightforward way to do it " -- why?
– Raphael
Jun 28 '17 at 20:50
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jun 28 '17 at 20:50
• Are you sure that this language is context-free?
– Raphael
Jun 28 '17 at 20:50
• Hello Raphael, There must be straightforward way to do it because this is a problem taken from last year's automata theory course exam and no lecturer is going to give a problem which takes like 1 hour to be solved. I'll revise the title, thanks! Jun 28 '17 at 21:05

First assume $n\ge m$. Then we can take $i=n-m$ and we have $i+k =l$, so strings are of the form
$a^i a^m b^m c^k d^k d^i$.
Then consider $n\le m$.