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
- thomas · alspaugh @ acm · org
-
-
Attribution