An 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\}$ 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 powers of $\Sigma$ :

• $\Sigma^0 = {\lambda }$ , where $\lambda$ stands for the empty string.
• $\Sigma^n = \{xy|x \in \Sigma, y \in \Sigma^{n-1}\}$ ($xy$ is the juxtaposition of $x$ and $y$ )

So, $\Sigma^n$ is the set of all strings formed from $\Sigma$ of length $n$ .