1

$$L=\{a^nb^mc^k:n≠m+k\}$$

I need a CFG for $L$. I believe I've got it down, but I would like any feedback if there is a better way of doing this one, or if I'm missing something.

$$\begin{align*} S&\to A\mid Xc\mid Yb\\ A&\to a\mid aA\mid aAYb\mid aAXc\\ X&\to c\mid Xc\mid aXc\mid aYb\mid\epsilon\\ Y&\to b\mid Yb\mid aYb\mid\epsilon \end{align*}$$

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

1 Answers1

1

HINT: You’re thinking in the right general direction, but the grammar is a bit too restrictive: it can’t generate $bc$. Let me suggest an alternative approach.

First design a context-free grammar that generates $L_0=\{a^nb^mc^k:n=m+k\}$; that should be fairly straightforward after your previous question. Change the name of the initial symbol of that grammar to $T$, let $S$ be the initial symbol of the grammar for the language that you actually want, and add the productions

$$\begin{align*} S&\to aT\mid aAT\mid Tc\mid TCc\mid Ub\mid UBb\\ A&\to a\mid aA\\ B&\to b\mid Bb\\ C&\to c\mid Cc\;. \end{align*}$$

Finally, add productions that make $U$ the initial symbol for a context-free grammar that generates the language $\{a^nb^n:n\ge 0\}$.

The derivations that start with one of the first two $S$ productions generate the words $a^nb^mc^k$ with $n>m+k$. Those starting with the third or fourth $S$ production generate the words $a^nb^mc^k$ with $n<m+k$ and $k\ge 1$. And those starting with one of the last two $S$ productions generate the words $a^nb^m$ with $n<m$.

Added: Here’s a context-free grammar that I think resolves all of the problems that we found in the comments. The new part is the production $S\to XBC$, and I’ve also removed a few redundancies.

$$\begin{align*} S&\to AT\mid TC\mid XB\mid XBC\\ T&\to aTc\mid aXb\mid\epsilon\\ X&\to aXb\mid\epsilon\\ A&\to a\mid aA\\ B&\to b\mid Bb\\ C&\to c\mid Cc\;. \end{align*}$$

Derivations that first apply $S\to AT$ produce the words of the form $a^nx$ for some $n\ge 1$ and $x\in L_0$. Derivations that first apply $S\to TC$ produce the words of the form $xc^n$ for some $n\ge 1$ and $x\in L_0$. Derivations that first apply the production $T\to XB$ produce the words of the form $a^mb^n$ for $0\le m<n$. And derivations that first apply the production $S\to XBC$ produce the words of the form $a^mb^nc^k$ for $0\le m<n$ and $k\ge 1$. This last category includes the words that we missed before, like $abbc$, that have extra $b$s and $c$s after a member of $L_0$ ending in $b$.

Community
  • 1
Brian M. Scott
  • 616,228
  • Ok...let me see if I follow. If I read carefully and did what you suggested, my production rules would be the following:

    $$\begin{align} S&\to aT\mid aAT\mid Tc\mid TCc\mid Ub\mid UBb\ T&\to aTc\mid aXb\mid \epsilon\ X&\to aXb\mid \epsilon\ U&\to aUb\mid \epsilon\ A&\to a\mid aA\ B&\to b\mid Bb\ C&\to c\mid Cc;. \end{align}$$

     – Kevin Robles Dec 11 '16 at 04:06
  • @Kevin: Yes, that looks okay. Note that you can replace $U$ by $X$ everywhere, since they have the same productions. – Brian M. Scott Dec 11 '16 at 04:14
  • Ok, yes, that's right. So it would end up as:

    \begin{align} S&\to aT\mid aAT\mid Tc\mid TCc\mid Xb\mid XBb\ T&\to aTc\mid aXb\mid \epsilon\ X&\to aXb\mid \epsilon\ A&\to a\mid aA\ B&\to b\mid Bb\ C&\to c\mid Cc; \end{align}

     – Kevin Robles Dec 11 '16 at 04:17
  • @Kevin: Looks good. – Brian M. Scott Dec 11 '16 at 04:18
  • I'm still not sure how I would go about generating $bc$. It might be that it's almost 1AM and my brain is fried. But I don't see a derivation of $bc$ with that CFG. – Kevin Robles Dec 11 '16 at 04:21
  • @Kevin: You’re right, and it’s partly my fault. Give me a few minutes to think about the best way to fix it. – Brian M. Scott Dec 11 '16 at 04:22
  • Not a problem at all, thank you! – Kevin Robles Dec 11 '16 at 04:23
  • @Kevin: It’s also missing things like $abbc$; the underlying problem is that we both missed the fact that we have to be able to generate $Tb^mc^n$ for all $m,n$ such that $m+n>0$. $U$ takes care of the $n=0$ case, and $C$ takes care of the case $Tb^mc^n$ with $m=0$, so we’re missing $Tb^mc^n$ with $m,n\ge 1$. Do you want to try your hand at filling that gap? – Brian M. Scott Dec 11 '16 at 04:31
  • Let me take a crack at it. – Kevin Robles Dec 11 '16 at 04:34
  • Would adding...

    \begin{align} S&\to XBTc \end{align}

    Do the trick?

     – Kevin Robles Dec 11 '16 at 04:53
  • @Kevin: That can give you $abbac$, which you definitely don’t want. At least for starters I wouldn’t try to integrate it too tightly with what you already have; I’d add $S\to TB$ and then have $V$ generate ${b^mc^n:m,n\ge 1}$. (It’s now midnight here, and I still have to fix dinner, so I may not be around again until tomorrow afternoon.) – Brian M. Scott Dec 11 '16 at 04:58
  • No worries, I'll keep taking a crack at it. Again, thanks for all your help so far, it has been invaluable. – Kevin Robles Dec 11 '16 at 05:04
  • @Kevin: You’re welcome; I’ll check back tomorrow. – Brian M. Scott Dec 11 '16 at 05:06
  • I've been trying but I've yet to come up with a solution. If there is any other hint you can give me, I'd appreciate it! – Kevin Robles Dec 11 '16 at 23:27
  • \begin{align} S&\to aA\mid Tb\mid Wc\ A&\to aAc\mid aBc\mid B\ B&\to aBc\mid aTb\mid \epsilon\ T&\to Tb\mid aTb\mid \epsilon\ W&\to aWc\mid aTc\mid Wc\mid T\mid \epsilon\ \end{align}

    What do you think of this solution? It generates $bc$. I think we've got it.

     – Kevin Robles Dec 11 '16 at 23:37
  • @Kevin: Sorry to be so late getting back; life got in the way a bit. This allows the derivation $$S\Rightarrow aA\Rightarrow aB\Rightarrow aaTb\Rightarrow aaTbb\Rightarrow aabb;,$$ which you don’t want. I’m going to be doing a couple of things at once most of the day, so I may not get back to this until this evening, but I will sort it out before I shut down for the day. – Brian M. Scott Dec 12 '16 at 19:46
  • @Kevin: Take a look at what I added to the answer, and let me know if you spot any problems. – Brian M. Scott Dec 13 '16 at 03:46