Help generating a grammar with {a,b,c} where the number of as and bs are different or bs and cs, or both

Question

w ∈ C*

"Generate a Grammar such that w contains strings of as followed by bs followed by cs such that there are either a different number of as and bs or a different number of bs and cs or both"

C= {a,b,c}

I am trying to do both. I'm having difficulties generating grammars, but I have understood that I should just write down some strings and from there try to generate some rules.

some of my strings are aabc, abbc, abcc, aabbbcc

I have produced the following rules:

$S\rightarrow aSbScS$

$S\rightarrow AS$

$S\rightarrow SB$

$S\rightarrow SC$

$S\rightarrow e$

$A\rightarrow a$

$B\rightarrow b$

$C\rightarrow c$

Did I do this right? And if not, what did I do wrong?

I am a language student and am trying to make my brain get used to such thinking, but I am somehow struggling with this.

Thank you.

Answer 1

Look at it like this, at least one of the following has to be true:

1. the number of $a$'s is larger than the number of $b$'s
2. the number of $b$'s is larger than the number of $a$'s
3. the number of $b$'s is larger than the number of $c$'s
4. the number of $c$'s is larger than the number of $b$'s

So we can make a grammar for each of these, and then simply combine them.

A grammar for the first condition looks like this:

\begin{align*} S_1&\to aXC\\ X&\to aX \mid aXb\mid\varepsilon\\ C&\to cC\mid\varepsilon \end{align*}

The first rule means there is at least one $a$ in the string, which is necessary. The second rule means that either we can add $a$'s to the front, or we can add both an $a$ to the front and a $b$ to the middle. Finally, the number of $c$'s doesn't matter.

Now we can make similar grammars with starting variables $S_2$, $S_3$ and $S_4$ for the other three conditions above, and then we can combine these with the rule \begin{align*} S\to S_1\mid S_2\mid S_3\mid S_4 \end{align*}