• Home
• Foundations
Thomas A. Alspaugh
Binary Strings

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