CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$}

Question

I'm practicing the following exercise for my exam: CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$} and I'm struggling a bit.

I've already solved {$a^nb^mc^l | n+m=l$} with production rules: $ S\rightarrow aSc | B|\varepsilon \\ B\rightarrow bBc|\varepsilon $,

which is almost the same except the positions of the symbols matter. In the other question the symbols can be anywhere which makes it a lot more difficult for me.

I have also solved: {$w\in{a,b}^* | $#$_a(w) = 2$#$_b(w)$} by using the production rules: $S \rightarrow aSbSa | aSaSb | bSaSa | SS | \varepsilon $, where the position doesn't matter.

I know that for every $a$ we have, we also need to create a $c$, and for every $b$ we have we need to create a $c$, however the position at which you create them don't matter, so you have a LOT of possibilities. So far I tried something like this $S \rightarrow aSc|bSc|T \\ T \rightarrow cTa | cTb | \varepsilon $

However these rules don't produce the string 'bccb' for example. I feel like I need a LOT of rules to create all the possibilities since the positions don't matter. Could someone give me a hint on how to tackle this?

EDIT: I just created an answer that worked but I find it not intuitive at all. Could this be simplified? $S \rightarrow cT | cTTc|TcTc|cTcT|TTcc|ccTT|TccT|\varepsilon \\ T \rightarrow aS | bS $

I found that you can remove a few of the productions which give: $S \rightarrow cT | Tc | ccTT | TccT | \varepsilon \\ T \rightarrow aS | bS$ However I just found this solution by just removing and adding stuff without any reasoning, which will make it hard to reproduce it for other questions

EDIT$^2$ eventhough my exercise checker says the last given CFG is correct, I do NOT think that it is. I can not seem to create the string "cccaaa"

Answer 1

You are interested in the language $L = \{w\in \{a,b,c\}^∗\mid \#_a(w)+ \#_b(w)= \#_c(w) \}$ but question how to haave the symbols in arbitrary order.

You have solved $\{w\in \{a,b\}^∗\mid \#_a(w)= 2\#_b(w)\}$ where the position does not matter.

I suggest you write a grammar for the simpler language $\{w\in \{a,c\}^∗\mid \#_a(w)= \#_c(w) \}$ where the order does not matter. Once you obtain a grammar you additionally allow that grammar to have $b$ at any position that is occupied by $a$, and you will get $L$.