Namespaces
Variants
Actions

Difference between revisions of "Alphabet"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(→‎References: isbn link)
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
A list (finite set) of letters (cf. [[Letter|Letter]]). An alphabet usually contains the letters which are required to develop a certain system of symbols or, as is sometimes said, a language. For two alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120201.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120202.png" />, their union <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120203.png" />, their intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120204.png" />, their difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120205.png" />, as well as the inclusion relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a012/a012020/a0120206.png" /> are defined in the obvious manner. For convenience, the concept of an empty alphabet, i.e. an alphabet without any letters, may also be considered.
+
{{TEX|done}}
 +
An '''alphabet''', in the context of [[Formal language|formal language theory]], is a finite [[Empty set|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 '''[[word]]s''') which are finite [[Sequence|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$

Latest revision as of 07:58, 18 November 2023

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=14016
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article