Give a regular expression

Question

Let Σ be {0, 1} Give a regular expression generating words over Σ containing an even number of 1’s or with a length which is multiple of 3.

I came up with this solution:

ε ( ((0*(10*10*)) + ((0+1) (0+1) (0+1)) )

and that's from this automata I drew up

but I am unsure if it's correct...

Answer 1

I think in the even number of $1$'s category, your NFA will miss strings of the form $110$ since you do not have an ending $0*$ at the end of your regex.

The other part of your regex only detects strings of length $3$, not multiples of 3. The correct thing would be to allow the second part of your regex to be repeated as many times as you want.

So, doing this step-by-step:

1. even number of ones: $\ (0^*(10^*)(10^*)0^*)^*$ The inner part of the regex allows for any number of zeroes before, after, and in between two $1$s. The outer $*$ allows for the two 1's matching regex to repeat as many times as desired, thereby allowing for an even number of 1's

2. strings of lengths of multiples of 3: $((0 + 1)(0 + 1)(0 + 1))^*$ By allowing the entire chunk to repeat, we allow strings of length $\ 0, 3, \ldots, 3n, n \in \mathbb{N}$.

Full regex: $$R = ((0^*(10^*)(10^*)0^*)^*) + ((0 + 1)(0 + 1)(0 + 1))^*$$

Answer 2

Hint. Your language is the union of two (regular) languages: the langage $L_1$ of all words containing an even number of $1$'s and the language $L_2$ of the words of length multiple of 3. Now just find a regular expression for $L_1$ and a regular expression for $L_2$ (this is easy in both cases) and just take the union of your two regular expressions.