1
$\begingroup$

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"

$\endgroup$
1
  • $\begingroup$ Please don't use "EDIT:" or just append more things to the end of a question. Instead, revise it so it reads well for someone who encounters it for the first time. Please figure out what exactly your question is, and be explicit in asking it. See cs.meta.stackexchange.com/q/657/755. $\endgroup$
    – D.W.
    Dec 14, 2023 at 20:06

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks! I indeed first created the grammar for the language #a=#c. Which was simpler and looked like: $ S \rightarrow aScS | cSaS | \varepsilon $ and then duplicated it but with a $b$ instead of an $a$ and added both together such that the total grammar is $ S \rightarrow aScS | cSaS | bScS | cSbS | \varepsilon $. This is more intuitive thanks! $\endgroup$
    – Jellyfish
    Dec 16, 2023 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.