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.

Improve this question
$\endgroup$
1
  • $\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. ♦
    Commented Nov 7, 2015 at 10:30

1 Answer 1

Reset to default
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*} $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.