alphabet Alphabet 2002-02-02 22:23:16 2004-09-13 13:26:02 Definition \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} An \emph{alphabet} $\Sigma$ is a nonempty finite set such that every string formed by elements of $\Sigma$ can be decomposed uniquely into elements of $\Sigma$. For example, $\{b,lo,g,bl,og\}$ is not a valid alphabet because the string $blog$ can be broken up in two ways: $\mbox{b lo g}$ and $\mbox{bl og}$. $\{\mathbb{C}a,\ddot{n}a,{\rm d},a\}$ \emph{is} a valid alphabet, because there is only one way to fully break up any given string formed from it. If $\Sigma$ is our alphabet and $n \in \mathbb{Z}^+$, we define the following as the \emph{powers of $\Sigma$}: \begin{itemize} \item $\Sigma^0 = {\lambda }$, where $\lambda$ stands for the empty string. \item $\Sigma^n = \{xy|x \in \Sigma, y \in \Sigma^{n-1}\}$ ($xy$ is the juxtaposition of $x$ and $y$) \end{itemize} So, $\Sigma^n$ is the set of all strings formed from $\Sigma$ of length $n$.