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

Sets

Relations

Correspondences

Ordered Sets

Lattices

Graphs

Powersets

Binary Strings

Logic

AIA

Greek

Glossary

Abstracts

Argument

Inquiry Cycle

Legal Relations

Presentations

Elicitation

Glossaries

Goals

i*

SCR

Tracing

Design Patterns

Javadoc

Java Packages

Java Types

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