alphabet

An alphabet $\mathrm{\Sigma }$ is a nonempty finite set such that every string formed by elements of $\mathrm{\Sigma }$ can be decomposed uniquely into elements of $\mathrm{\Sigma }$.

For example, $\{b,lo,g,bl,og\}$ is not a valid alphabet because the string $blog$ can be broken up in two ways: b lo g and bl og. $\{ℂa,\ddot{n}a,\mathrm{d},a\}$ is a valid alphabet, because there is only one way to fully break up any given string formed from it.

If $\mathrm{\Sigma }$ is our alphabet and $n\in {\mathbb{Z}}^{+}$, we define the following as the powers of $\mathrm{\Sigma }$:

• ${\mathrm{\Sigma }}^0=\lambda$, where $\lambda$ stands for the empty string.

• ${\mathrm{\Sigma }}^n=\{xy|x\in \mathrm{\Sigma },y\in {\mathrm{\Sigma }}^{n-1}\}$ ($xy$ is the juxtaposition of $x$ and $y$)

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

Title	alphabet
Canonical name	Alphabet
Date of creation	2013-03-22 12:15:58
Last modified on	2013-03-22 12:15:58
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	7
Author	mathcam (2727)
Entry type	Definition
Classification	msc 03C07
Synonym	powers of an alphabet
Related topic	KleeneStar
Related topic	Substring
Related topic	Language
Related topic	HuffmanCoding
Related topic	Word