# Alphabet

An **alphabet**, in the context of formal language theory, is a finite non-empty set. Typically it is denoted $\Sigma$ or $V$ (where $V$ stands for vocabulary). Examples range from the binary alphabet $\{0,1\}$ to the keywords for a particular programming language.

The elements of an alphabet are referred to as the **letters** (or **symbols**) of the alphabet. From an alphabet we may obtain **strings** (or **words**) which are finite sequences of letters over $\Sigma$. The empty string, denoted $\lambda$ or $\epsilon$, is also considered a string containing no letters.

The set of all words over $\Sigma$ (including the empty word) is denoted $\Sigma^*$ and is referred to as the **Kleene star (or closure)** of $\Sigma$ (or **monoid closure**) after the American mathematician S. C. Kleene. The set $\Sigma^* \setminus \{ \lambda\}$ is denoted $\Sigma^+$ and is referred to as the **Kleene plus** (or **semigroup closure**) of $\Sigma$. The names monoid and semigroup closure being justified by $\Sigma^*$ and $\Sigma^+$ forming a monoid and semi-group under concatenation respectively.

## References

[1] Arto Salomaa, *Formal Languages*, (1973): $\S 1$

[2] Michael A. Harrison, *Introduction to Formal Language Theory*, (1978): $\S 1.2$

[3] John E. Hopcroft and Jeffrey D. Ullman, *Introduction to Automata Theory, Languages, and Computation*, Addison-Wesley Publishing, Reading Massachusetts, (1979). ISBN 0201-02988-X.

[4] György E. Révész, *Introduction to Formal Languages*, (1991): $\S 1.1$

[5] Grzegorz Rozenberg and Arto Salomaa, *Handbook of Formal Languages: Volume 1. Word, Language, Grammar*, (1997): $\S 1.2$

[6] Dan A. Simovici and Richard L. Tenney, *Theory of Formal Languages with Applications*, (1999): $\S 2.1$

[7] Keijo Ruohonen, *Formal Languages*, (2009): $\S 1.1$

[8] John Martin: *Introduction to Languages and the Theory of Computation* (2010): $\S 1.5$

**How to Cite This Entry:**

Alphabet.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Alphabet&oldid=38525