Context-free grammar for binary words I am supposed to create CFG for this languague:

$L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$

where $|w_b|$ is count of terminals $b$ in $w$.

For example:

aa - OK, no 'b'

abb - wrong, only 2 'b'

aaabbb - OK, 3 times 'b'

aababbb - wrong, 4 times 'b'

abbbbbaaa - wrong, 5 times 'b'

abababbbaaab - OK, 6 times 'b'

and so on...

I can't come up with any solution. Any advice?



My goal is to design context-free grammar, not automaton or regular expression (i don't know how to design automatons or RE yet).

What about CFG

G = {{S,A}, {a,b}, R, S}


where R rules are:

1] S -&gt; S A b A b A b A S
2] S -&gt; A
3] S -&gt; ε
4] A -&gt; a A
5] A -&gt; ε


Explanation:

rule 2] is for cases when there are no 'b' symbols in w

rule 3] is for case of empty string

rule 4] is for adding 'a' symbols between 'b', e.g. baaaabab, babaab

rule 5] is for cases, when there are multiple 'b' next to each other, e.g. abbbaaa



Is this CFG ok?
Hint: A string with exactly one $a$ would look like this:
$$
(any\ number\ of b's)\,a\,(any\ number\ of b's)
$$
and a grammar to generate the language of these strings is $S\rightarrow AaA,\ \  A\rightarrow aA\mid \epsilon$.

Generalize.