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$