Structural Induction help Give a recursive definition of the set of bit strings that
contain twice as many 0s as 1s. please any guidance would be appreciated this is a hw problem.
 A: This might work. 
Let $\mathscr U$ be the set of all bit strings.  
I would have as my initial set $B = \{001, 010, 100  \}$. Then define unary functions $ f_1, f_2, g_1, g_2, g_3 $ on $\mathscr U$ such that for every $a \in \mathscr U$, 
$ f_1(a) = a1 $
$ f_2(a) = 1a $
$ g_1(a) = 00a $
$ g_2(a) = a00 $
$  g_3(a) = 0a0 $
Thet let $\mathscr C$ be the set of strings that have twice as many $0$s as $1$s. Then, 


*

*$B \subseteq \mathscr C  $

*$a \in \mathscr C \implies (g_j\circ f_i)(a) \in \mathscr C$ for  $i \in \{ 1,2\} $ and $j \in \{1,2,3 \} $

*$a \in \mathscr C \implies (f_i\circ g_j)(a) \in \mathscr C$ for  $i \in \{ 1,2\} $ and $j \in \{1,2,3 \} $


Don't have a proof though. 
A: $$\text{TwiceAsManyZeros}(X) = \begin{cases}
\text{true} & \text{ if } X = \epsilon \\
\text{TwiceAsManyZeros}(X \text{ Sans } 001) & \text{ if } 001 \subseteq X \\
\text{TwiceAsManyZeros}(X \text{ Sans } 010) & \text{ if } 010 \subseteq X \\
\text{TwiceAsManyZeros}(X \text{ Sans } 100) & \text{ if } 100 \subseteq X \\
\text{false} & \text{ otherwise}
\end{cases}$$
Here is used:


*

*$\epsilon$ to represent the empty string

*$A \text{ Sans } B$ to represent string $A$ with any 1 occurrence of substring $B$ deleted

*$A \subseteq B$ to be true iff $A$ is a contiguous substring of $B$

