Recursively defining the set of bit strings set having more zeros than ones Question: 
Recursively define the set of bit strings that have more zeros than ones.
I tried it this way:
$\Sigma\subset \{0,1\}^*$
Basis step: $0 \in \Sigma$
Recursive step: For any $x\in \Sigma$, $00x1\in L$
Is it a valid answer?
 A: Denote by $\Sigma$ the set of all finite binary strings, including the empty string $\oslash$. In the follwing $x$, $y$, $\ldots$ are variables for strings, and juxtaposition denotes concatenation.
Strings containing more zeros than ones  are called admissible. The language $L$ consisting of all admissible strings can be recursively generated as follows:
(i)$\quad 0\in L$,
(ii)$\quad x\,y\in L\ \rightarrow\ x\,0\,y,\ x\,0\,1\,y,\ x\,1\,0\,y\in L$.
Note that in (ii) $x$ or $y$ may be $=\oslash$. – It is obvious that all strings so generated are admissible. Conversely: The admissible strings of length $\leq2$ are $0$ and $0\,0$, and are indeed produced by (i) and (ii). Assume now that all admissible strings of length $\leq n$ are produced by (i) and (ii). If an admissible string $z$ has length $n+1$ and does not consist solely of zeros it contains $0\,1$ or $1\,0$ as a substring. It then can  be produced using (ii) and an admissible string $x\,y$ of length $n-1$.
A: HINT: Your basis step is fine (except that you mean $0\in L$), but the recursive step should show how to build longer members of $L$ from shorter ones. For instance, you want clauses that say that if $x\in L$, then $0x\in L$ and $x0\in L$: these clauses let you add any number of $0$’s to either end of a string that’s already in $L$. But of course you must also be able to add $1$’s. If you start with some $x\in L$, you can add a $1$ at either end provided that you add a $0$ as well. You could have, for instance, a clause that says that if $x\in L$, then $0x1\in L$. But this isn’t the only way to add a $1$ (and a compensating $0$) to a string in $L$, even if — as is sufficient — you limit yourself to additions on the ends. You’ll need several more clauses of that general type.
A: It might be a little late to answer but this would be another way to answer it.
Basic Step: $0 \in S$.
Recursive Step: If $x, y \in S$ then $xy \in S$, $x1y \in S$, $1xy \in S$, $xy1 \in S$.
A: To expand on your recursive step, I believe you'll need:
$0x \in S$, $x0 \in S, 01x\in S, 10x\in S, 1x0\in S, 0x1\in S, x01\in S, x10\in S$, for any $x \in \Sigma$ 
And your $\Sigma$ should really denote the set you're trying to define, that is the set of bit strings having more zeros than ones.
