Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$

Let $\mathrm{\Sigma }$ be a finite set, called an alphabet. For each natural number $n$, a word of length $n$ over $\mathrm{\Sigma }$ is a function $w:n\to \mathrm{\Sigma }$, equivalently an element of ${\mathrm{\Sigma }}^n$ (The set $B^A$ of all functions $A\to B$). Writing $w(i)=a_i$ for $i<n$, we display the word as $a_0{a}_1\cdots a_{n-1}$. This is the same finite-word convention already used in Finite words, contiguous factors, avoidance and proper-prefix states.

The unique word of length $0$ is the empty word $\epsilon$.

If $u:m\to \mathrm{\Sigma }$ and $v:n\to \mathrm{\Sigma }$ are words, their concatenation is the word $uv:(m+n)\to \mathrm{\Sigma }$ defined by $(uv)(i):=\{\begin{array}{ll}u(i),& i<m,\\ v(i-m),& m\le i<m+n\mathrm{.}\end{array}$

The set of all finite words over $\mathrm{\Sigma }$ is ${\mathrm{\Sigma }}^{\ast }:={\bigcup }_{n\in \mathbb{N}}{\mathrm{\Sigma }}^n,$ an indexed union in the sense of ${\bigcup }_{i\in I}{A}_i:=\bigcup \{A_i:i\in I\}$, and ${\bigcap }_{i\in I}{A}_i:=\bigcap \{A_i:i\in I\}$ for $I\mathrm{\ne }\mathrm{\varnothing }$.

• A word is an element of ${\mathrm{\Sigma }}^{\ast }$, not a subset of $\mathrm{\Sigma }$. The symbols of the alphabet are the values of the function; the word itself is the whole finite sequence.

• For the binary alphabet $\{0,1\}$ the notation $\{0,1{\}}^{\ast }$ means every finite binary word, including $\epsilon$.