Structural Induction help

Question

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.

Answer 1

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.

Answer 2

$$\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$