(Last modified Thu Feb 14 16:20 2008)

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 A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences