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:

Valid XHTML 1.0 Strict
Valid CSS!
2010Feb24We20:59
Thomas A. Alspaugh