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?

Improve this question
$\endgroup$
4
  • 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, 2017 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, 2017 at 20:50
  • $\begingroup$ Are you sure that this language is context-free? $\endgroup$
    – Raphael ♦
    Jun 28, 2017 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, 2017 at 21:05

1 Answer 1

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

Improve this answer
$\endgroup$
2
  • 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, 2017 at 23:44
  • $\begingroup$ Exactly what i was looking for! Thank you, Hendrik! $\endgroup$
    – Zarrie
    Jun 29, 2017 at 5:58

Your Answer

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

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