I am trying to find a regular expression for {Strings whose number of 0s is not divisible by 4}, with and without the use of complement.

Question

With use of a complement I found:

$$\{ \text{Strings whose number of 0s is divisible by 4\}}^{C} = $$ $$\{\{\{1\}^*\cdot \{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{1\}^*\}^*\}^{C}$$

I haven't been able to find a regular expression that does not use complement.

Answer 1

Let $L = (1^*01^*01^*01^*01^*)^* = \{u \in \{0,1\}^* \mid |u|_0 \equiv 0 \bmod 4 \}$. Then the language you are looking for is $$ L(01^* + 01^*01^* + 01^*01^*01^*). $$ Can you see why?