Question

(b) Find a concise, explicit description for the set A, which is defined by 1 ∈ A, and if a and B are bit strings in A, then aB ∈ A, 0aB ∈ A, a0B ∈ A, and aB0 ∈ A.

Answer 1

Let Z be a set of bit strings in which number of 1-bits is more than number of 0-bits. Consider a function on bit strings f(X) = (the number of 1-bits in X) – (the number of 0-bits in X), where X be an arbitrary bit string: X=(x₁, x₂, …, x_N). So Z is a set of bit strings X that f(X) >=1. We prove that A = Z.

Statement (1). If X$\in$A then X$\in$Z.

Prove this statement by induction over N - the length of the string X.

1.1. Case N=1. As f(0) = -1, f(1) = 1, therefore, 1$\in$ Z, 0$\notin$ Z. Clearly, 0$\notin$ A, and, by condition, 1$\in$A, so the base of induction is proved.

1.2. Let the statement (1) is proved for any string X$\in$ A of the length less than N. Consider a string X of the length N. By condition, X is of one of the form: X = aB or  X = 0aB or X = a0B or X = aB0, where a$\in$A, B$\in$A. Clearly, that the length of both strings a and B is less than N. By induction, f(a)>=1 and f(B)>=1.

If X=aB then f(X) = f(a)+f(B)>=2, and, hence, X$\in$Z.

If X = 0aB or X = a0B or X = aB0 then f(X) = f(a)+f(B) -1 >=1, and, hence, X$\in$Z.

So, the statement (1) is proved for strings of length N, and, by induction, for strings of any length.

Statement (2). If X$\in$Z and f(X) >= 2 then there exist strings a$\in$Z and B$\in$Z that X=aB.

2.1. Let n be a minimal index that f(x₁, x₂, …, x_n) >= 1. If x_n = 0 then f(x₁, x₂, …, x_n-1)>=2 and this contradicts to condition that n is a minimal index that f(x₁, x₂, …, x_n) >= 1. Therefore, x_n = 1.

If f(x₁, x₂, …, x_n) >= 2, then f(x₁, x₂, …, x_n-1) = f(x₁, x₂, …, x_n) -1 >=1 and this contradicts to condition of the minimality n. Therefore, f(x₁, x₂, …, x_n) = 1.

Let a = (x₁, x₂, …, x_n), B = (x_n+1, x_n+2, …, x_N). Then X = aB, f(a) =1 and f(B) = f(X) – f(a) >= 1.

So, a$\in$Z, B$\in$Z and X=aB and the statement is proved.

Statement (3). Any string X$\in$ Z is an element of A.

Again, the proof will be based on induction on N - the length of the string X.

3.1. If N=1, f(X)>=1 then X=(1), and X$\in$A by condition.

3.2. Let the statement (3) is proved for any string X$\in$A with the length less than N. Consider several cases:

(a) If f(X)>=2 then, by statement (2), there exist strings a$\in$Z and B$\in$Z, that X=aB. As the length of a and B less than N, by induction, they are elements of A. Then X = aB belongs to A by condition.

(b) If f(X)=1 and x₁=0 then f(x₂, …, x_N)=2 and, by statement (2), there exist strings a$\in$Z and B$\in$Z, that (x₂, …, x_N)=aB. As the length of a and B less than N, by induction, they are elements of A. Then X = 0aB belongs to A by condition.

(c) If f(X)=1 and x_N=0 then f(x₁, …, x_N-1)=2 and, by statement (2), there exist stringsa$\in$Z and B$\in$Z, that (x₂, …, x_N)=aB. As the length of a and B less than N, by induction, they are elements of A. Then X = aB0 belongs to A by condition.

(d) If f(X)=1 and x₁=x_N=1 then f(x₂, …, x_N-1)=-1.

Let n>=2 be a minimal index that f(x₂, …, x_n) <= -1. Then f(x₂, …, x_n-1) >=0, x_n=0 and f(x₂, …, x_n-1) =0.

Let a =(x₁,…,x_n-1) and B = (x_n+1,…,x_N). Then X = a0B, f(a)=1 and f(B) = f(X)-f(a)+1 = 1.

By induction, a and B are elements of A. Then X = a0B belongs to A by condition.

As (a)-(d) form a complete system of cases, the statement (3) is proved for strings of the length N, and, by induction, for any strings.

It follows from (1) and (3) that A=Z, that is, A is a set of bit strings in which number of 1-bits is more than number of 0-bits.

Answer. A is a set of bit strings in which the number of 1-bits is more than the number of 0-bits.