Alphabets and Strings

Before we can talk about languages in the formal sense, we need the alphabet
and the strings.

Definition 7.1.1 (notes p. 118): An alphabet $\Sigma$ is a finite set. Its
elements are called characters or symbols. An $n$-tuple $s \in \Sigma^n$
is called a string (of length $n$ over $\Sigma$).

Definition 7.1.4: The length $|s|$ of string $s \in \Sigma^n$ is $n$.

Definition 7.1.2: $\Sigma^0 = \{\langle\rangle\}$, which is the unique 0-tuple.
We denote this string by $\epsilon$ and call it the empty string.

Sets vs strings: $\{1, 2, 3\} = \{3, 2, 1\}$ as sets, but
$\langle 1, 2, 3 \rangle \neq \langle 3, 2, 1 \rangle$ as strings. Order matters
for strings, but not for sets.

Concatenation (Definition 7.1.5): for $s \in \Sigma^n, t \in \Sigma^m$:

We often write $s + t$ or simply $st$ for concatenation. Note $|st| = |s| + |t|$
and $s\epsilon = \epsilon s = s$ (identity element).

A common shorthand (Definition 7.1.10): $c^{[n]}$ means the character $c$ repeated
$n$ times. So $a^{[3]} = aaa$.

Strings are the atoms of formal languages — every program, every formula, every
sentence is a string over some alphabet.