Binary Strings thomasalspaugh.org/pub/fnd/binaryString.html

A binary string is a sequence of 0's and 1's.

Let Σ be the set {0,1}.  Then the set of finite binary strings is written as Σ*, and the set of finite and infinite binary strings is written as Σ**.  (The same notation is used for other alphabets other than 0 and 1.)

Σ* can be ordered by the prefix relation, as can Σ**:  for u,vΣ* (Σ**), u is a prefix of v if either u=v or u is a finite initial substring of v.  We write u≤v if u is a prefix of v, and u||v if neither u nor v is a prefix of the other (some authors write u#v).

Here are some examples:

• The empty string ε is a binary string.  ε is in both Σ* and Σ**.
• 0 and 1 are finite binary strings, and are in both Σ* and Σ**, as are all finite binary strings.
• 010101... is an infinite binary string.  It is in Σ** but not Σ*.
• 0 ≤010101...
0 is a prefix of 010101....
• 1 || 010101...
1 is not a prefix of 010101..., nor is 010101... a prefix of 1; they are incomparable.  In fact, 010101... is not a prefix of anything (because it is not finite).
• 00 ≤ 000
• 00 || 0101
2010Feb24We20:59
Thomas A. Alspaugh