This is for a homework assignment. The prompt is:
Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc.
I've been stuck on this for hours. So far I've tried:
S → aS | bS | bA
A → cA | cB
B → aB | bB | bC | λ
C → cC | cS
but this doesn't account for strings such as ccccbc. Then I tried:
S → A | B
A → aS | cS
B → bB | aS | bC
C → cC | cD
D → E | λ
E → F | G
F → aE | cE
G → bG | aE | bH
H → cH | cS
Which I think might be right but I'm not sure. Am I close/correct and if so how can I verify this?
I started from scratch by designing a DFA to recognize the language, because this seemed the simplest approach:
If you work through it, you’ll see that this automaton is in state $2$ immediately after any odd number of substrings $bc$ and in state $0$ immediately after any even number of substrings $bc$.
Then I simply designed the grammar from the DFA:
$$\begin{align*} &S\to aS\mid cS\mid bB_1\\ &B_1\to aS\mid bB_1\mid cC\mid c\\ &C\to bB_2\mid b\mid aC\mid cC\mid c\\ &B_2\to aC\mid a\mid bB_2\mid b\mid cS \end{align*}$$
$S$ corresponds to state $0$, $B_1$ to state $1$, $C$ to state $2$, and $B_2$ to state $3$, and each production represents one transition in the DFA. For instance, the production $C\to bB_2$ represents the transition
$$2\overset{b}\longrightarrow 3\;,$$
and the production $B_1\to c$ represents halting in the acceptor state $2$ after the transition
$$1\overset{c}\longrightarrow 2\;.$$