Alphabets and Strings

Alphabets

Definition

An alphabet is a finite set $\Sigma$ whose elements are called symbols.

Examples

• $\{0, 1\}$: binary alphabet
• $\{a, b, c, \ldots, z\}$: lowercase English letters
• $\{0, 1, 2, \ldots, 9\}$: decimal digits
• ASCII character set (finite)
• $\{\} = \emptyset$: the empty alphabet

Non-examples

• $\mathbb{N}$: infinite, not an alphabet
• $\mathbb{R}$: infinite, not an alphabet

Strings

Definition

A string (or word) over alphabet $\Sigma$ is a finite sequence of symbols from $\Sigma$.

• Strings are written without punctuation: $abba$, $0011$
• The length of string $w$ is written $|w|$
• The empty string (length 0) is written $\varepsilon$ or $\lambda$

Formal Definition

A string of length $n$ is a function $w : [n] \to \Sigma$, where $[n] = \{0, 1, \ldots, n-1\}$.

The empty string is the unique function $[0] \to \Sigma$.

Examples

Over $\Sigma = \{a, b\}$:

• $\varepsilon$: empty string, $|\varepsilon| = 0$
• $a$: length 1
• $abba$: length 4
• $aaaa$: length 4

The Set of All Strings

Definition

$\Sigma^*$ is the set of all strings over $\Sigma$, including $\varepsilon$.

$\Sigma^* = \{w : w \text{ is a string over } \Sigma\} = \bigcup_{n \geq 0} \Sigma^n$

where $\Sigma^n = \{w : |w| = n\}$ is the set of length-$n$ strings.

Special Cases

• If $\Sigma = \emptyset$: $\Sigma^* = \{\varepsilon\}$ (only the empty string)
• If $\Sigma = \{a\}$: $\Sigma^* = \{\varepsilon, a, aa, aaa, \ldots\}$

Distinguishing Notation

Symbol	Meaning
$\emptyset$	The empty set
$\{\varepsilon\}$	The set containing the empty string
$\varepsilon$	The empty string itself

These are three distinct objects!

Concatenation

Definition

The concatenation of strings $u$ and $v$, written $uv$, is the string formed by appending $v$ to $u$.

$|uv| = |u| + |v|$

Properties

• Identity: $u\varepsilon = u = \varepsilon u$
• Associativity: $(uv)w = u(vw)$

Concatenation is NOT commutative: in general $uv \neq vu$.

Examples

If $u = ab$ and $v = ba$:

• $uv = abba$
• $vu = baab$
• $uu = abab$
• $u^3 = ababab$

Powers

For a string $u$ and $n \geq 0$:

$u^n = \underbrace{uu\cdots u}_{n \text{ times}}$

By convention, $u^0 = \varepsilon$.

Strings Form a Monoid

Algebraic Structure

$(\Sigma^*, \cdot, \varepsilon)$ is a monoid:

• Binary operation: concatenation
• Identity element: $\varepsilon$
• Associative: $(uv)w = u(vw)$

Not a Group

Strings do not generally have inverses under concatenation.

If $uv = \varepsilon$, then $u = v = \varepsilon$.

Free Monoid

$\Sigma^*$ is the free monoid on $\Sigma$: every monoid generated by $\Sigma$ is a quotient of $\Sigma^*$.

Substrings and Prefixes

Substring

$u$ is a substring of $w$ if $w = xuy$ for some strings $x, y$.

Prefix

$u$ is a prefix of $w$ if $w = uv$ for some string $v$.

Suffix

$u$ is a suffix of $w$ if $w = vu$ for some string $v$.

Examples

For $w = abcd$:

• Prefixes: $\varepsilon, a, ab, abc, abcd$
• Suffixes: $\varepsilon, d, cd, bcd, abcd$
• Substrings include: $bc$, $b$, $\varepsilon$, $abcd$

---

Summary

• An alphabet $\Sigma$ is a finite set of symbols
• $\Sigma^*$ is the set of all finite strings over $\Sigma$
• Concatenation is associative with identity $\varepsilon$
• $(\Sigma^*, \cdot, \varepsilon)$ forms a monoid
• $\emptyset$, $\{\varepsilon\}$, and $\varepsilon$ are distinct