1
$\begingroup$

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.

Can somebody help me, please?

$\endgroup$
  • 1
    $\begingroup$ "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? $\endgroup$ – Raphael Jun 28 '17 at 20:50
  • $\begingroup$ 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! $\endgroup$ – Raphael Jun 28 '17 at 20:50
  • $\begingroup$ Are you sure that this language is context-free? $\endgroup$ – Raphael Jun 28 '17 at 20:50
  • $\begingroup$ 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! $\endgroup$ – Zarrie Jun 28 '17 at 21:05
2
$\begingroup$

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$.

You can do a CFG for that.

Then consider $n\le m$.

$\endgroup$
  • 1
    $\begingroup$ Actually examples of "letter tricks" like this are given in my answer to a reference question: cs.stackexchange.com/questions/18524/… $\endgroup$ – Hendrik Jan Jun 28 '17 at 23:44
  • $\begingroup$ Exactly what i was looking for! Thank you, Hendrik! $\endgroup$ – Zarrie Jun 29 '17 at 5:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.