Regular grammar with parity

Question

Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc.

How can you limit the number of recursions for a regular grammar to be a specific parity?

So I came up with this.

S > bA | aS | Sc | bS
A > cB
B > bC | bB | aB
C > cD
D > bE
E > cB | Ea | cE | terminate

Answer 1

An odd parity means at least one bc will occur. So start with that.

Then, you need to surround it on the left and right with the different possible combinations that can occur.

That is the right idea. However, it does not provide for a way to terminate with just the string "bc".

Also, the following is possible with the machine you wrote:

S -> bA -> bcB -> bcbC -> bcbcD -> bcbcbE -> terminate.

In this case, there is an even under of bc's.

Should I give you the answer, or would you like another try?

Edit 2: Alright, here is the answer:

 S -> aS | cS | bT //even number of bc's has been encountered
 T -> aS | bT | cA //even number of bc's, and then b some time after
 A -> aA | bB | cA | END //odd number of bc's has been encountered
 B -> aA | bB | cS | END //odd number of bc's, and then b some time after

This is as simple as it gets, and very intuitive.

---

EDIT: The below is what we called regular grammar; what is described in the updated post is something we called Finite State Machine. I will put my answer to that on top, leaving my original answer below.

For example:

$c^*(bcbc)^*$, $b^*(bcbc)^*$

However, since you don't wish for bc to occur together, you do not wish to do $[c^*(bcbc)^* b^*(bcbc)^* a^*(bcbc)^*]^*$. You will need at least one $a$ after each $b$ and before the next $c$. So something like: $[c^*(bcbc)^* b^*(bcbc)^*a a^*(bcbc)^*]^*$

Let me know if you need further hints.