Context Free Diagram - Unequal a's and b's and c's

116 Views Asked by At

$$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*}$$

1

There are 1 best solutions below

17
On

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