Regular expression with binary alphabet.

Question

Consider a binary alphabet. We want to find regular expression, which determine sequences , where every length of block of zeroes divide by 3.

My attempt : $1^* ((000)^* 1^*)^* $. Does it right, or not?

Answer 1

If I understand your question and your comments, you are looking for an unambiguous regular expression for your language $L$. In this case, just use $(1 + 000)^*$. Indeed the language $\{000, 1\}$ is a code (in fact it is a bifix code, that is, a prefix code and a suffix code).

For each $n \geqslant 0$, let $L_n = L \cap \{0, 1\}^n$. Then the generating series of $|L_n|$ is $$ \sum_{n \geqslant 0} |L_n|\ t^n = (t +t^3)^* = \frac{1}{1 - t- t^3} $$ I let you find the recurrence relation defining the coefficients $|L_n|$, since it was not part of your original question.

Answer 2

Yes, your answer works, but could be simplified as $((000)^*1^*)^*$.