[Math] Give a recursive definition for the set of finite binary strings with an even number of 0s followed by 1s

computer sciencediscrete mathematics

Give a recursive definition for the set $S$ consisting of finite bit-strings containing an even number of $0$s, and all $0$s (if present) appear before all $1$s. That is, $001\in S$ and $1\in S$, but $01111\not\in S$, and $01100011\not\in S$.

I was thinking the basis step would be empty string is a member of $S$, but I don't really know how to do the problem.

Best Answer

The base case is the empty string, which is a member of S.

Now everything that has 2 zeros before an existing member of S is also a member of S.

Everything that has 1 one after an existing member of S is also a member of S.

This should give you every member of S.

(If you don't want to use the empty string as a base case because it's not a finite bit-string, you could also use two separate base cases, 00 and 1, and still apply the previous two rules.)