0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 7 '15 at 10:30
3
$\begingroup$

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*} $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy