String

A string over an alphabet is a finite sequence of symbols drawn from that alphabet.

Formal definition

Given an alphabet $\Sigma$, a string (or word) of length $n \geq 0$ over $\Sigma$ is a function $w : \{1, 2, \ldots, n\} \to \Sigma$. The length is denoted $|w| = n$. The unique string of length zero is the empty string, written $\varepsilon$.

The set of all strings of length exactly $n$ over $\Sigma$ is $\Sigma^n$. The set of all finite strings is the Kleene closure

Concatenation is the operation $\cdot : \Sigma^* \times \Sigma^* \to \Sigma^*$ that appends one string to another. Under concatenation with identity $\varepsilon$, $\Sigma^*$ forms a monoid — the free monoid generated by $\Sigma$.

Intuition

A string is what you get when you take finitely many symbols from an alphabet and put them in a specific order. The empty string $\varepsilon$ is a frequent source of bugs in proofs and implementations because it is simultaneously the unique length-zero object and the identity of concatenation. Treat it as a first-class citizen from the start; do not default to assuming strings have at least one character.

The finiteness is load-bearing. Infinite sequences over $\Sigma$ exist — they are called $\omega$-words and live in $\Sigma^\omega$ — but they require a different theory altogether (Büchi automata and $\omega$-regular languages). For the automata theory and computability covered on sibling pages, every input is a finite string.

Notes

A language over $\Sigma$ is any subset $L \subseteq \Sigma^*$. Formal language theory studies which subsets can be specified by which kinds of machines.

The name Kleene closure honors Stephen Kleene, who introduced the operation in his 1951 RAND memorandum on regular expressions.