0

I've searched and searched and can't find a similar CFG. I've got this language:

$$L=\{a^nb^mc^rd^t:n+m=r+t\}$$

Basically, I have to have the same amount of $a$'s and $b$'s as I have $c$'s and $d$'s. I've gotten close, but the production rules I've come up with don't take into consideration the order. i.e. $badc$ is not a valid string in the language. The $a$'s must come before the $b$'s and the $c$'s before the $d$'s.

Any help would be greatly appreciated.

PS Sorry I don't know how to use the math formatting.

Brian M. Scott
  • 616,228
Kevin Robles
  • 13

1 Answers1

0

HINT: I’ll get you started with the productions $S\to aSd$, $S\to aXc$, $S\to bYd$, and $S\to bZc$. The first lets you generate strings of the form $a^nSd^n$; if you then apply the third, say, you get $a^nbYd^{n+1}$. Now you may want $Y$ to pop out matched $b$s and $d$s, so you want a production $Y\to bYd$; with that you can get strings of the form $a^nb^mYd^{n+m}$. At some point, though, you’ll want to be able to switch to popping out $b$s and $c$s, so you’ll want a production $Y\to bZc$. (We might as well use $Z$ again, since it’s already set up for the purpose.) Can you see how to fill in the details and add the necessary productions to get what you want? There’s still quite a bit to be done, but I think that I’ve at least suggested all of the necessary ideas.

Brian M. Scott
  • 616,228
  • Thank you so much! I was a bit stuck for a while but your hint led me on. This is what I've got and it seems to work.

    $S\to aSd$, $S\to aXc$, $S\to bYd$, $S\to bZc$, $X\to aXc$, $X\to bZc$, $Z\to bZc$, $Y\to bYd$, $Y\to bZc$.

    I was basically having a hard time realizing that with my productions rules I had to force, for example, that once you had a $c$, you can't produce any more $d$'s. If you want $j$ amount of $d$'s, produce them first with $a$'s or $b$'s. But if you put a $b$, then you limit yourself to only more $b$'s etc etc etc.Thanks so much.

     – Kevin Robles Dec 10 '16 at 21:48
  • @Kevin: You’re welcome! You definitely have the right idea. You’ll need a few more productions: at the moment all of your righthand sides still contain a non-terminal, and you need to be able to get rid of them. For instance, you’ll need $S\to\lambda$ (or $S\to\epsilon$, depending on your notation) in order to get the empty string. – Brian M. Scott Dec 10 '16 at 21:53
  • Ah, yes, forgot to put the productions with the epsilons. That would basically be S, X, Y, Z all $\to$ $\epsilon$ . – Kevin Robles Dec 10 '16 at 21:55
  • @Kevin: Looks good! – Brian M. Scott Dec 10 '16 at 21:55
  • thanks!!! It is definitely not easy to learn this stuff by yourself. But the help is very much appreciated. – Kevin Robles Dec 10 '16 at 21:56
  • @Kevin: You’re most welcome. Even though this site is nominally supposed to be creating a sort of reference library of useful questions and answers, I think that one of its most valuable functions is helping folks who are trying to learn on their own. That kind of resource just didn’t really exist until quite recently. – Brian M. Scott Dec 10 '16 at 21:59