Recursively defining the set of bit strings set having more zeros than ones

Question

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?

Answer 1

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

Answer 2

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.