# Example Context free grammar

Is there a nice way to give context free grammar for $$\{a^nb^ma^kb^l:n+m=k+l\}?$$

From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack if we see a, pop + from stack if we see b and accept if you have empty stack.

• Every decent automata theory textbook gives a description of how to convert a PDA to a CFG. So, simply apply that construction and you'll get a CFG for that language. There's little point in us repeating the description that construction here, and a question that says "please run standard algorithm X on my particular input Y for me" seems of unclear value (to me) -- better for you to run it yourself. – D.W. Nov 7 '15 at 10:30

## 1 Answer

Here is a simple grammar: \begin{align*} & S \to aSb|U|V \\ & U \to aUa|T \\ & V \to bVb|T \\ & T \to bTa|\epsilon \end{align*}

• And why would that be correct? – Raphael Nov 5 '15 at 20:46
• Just a feeling. The OP didn't ask for a proof, just for a grammar. – Yuval Filmus Nov 5 '15 at 20:56
• Of course it is indeed correct. Very nice job, Yuval. – Rick Decker Nov 6 '15 at 14:38
• Looks like something Arul can use to practice structural induction on. – G. Bach Nov 6 '15 at 14:52
• @Arul There is an algorithm for converting PDA to CFG. You could run it. – Yuval Filmus Nov 7 '15 at 23:04