Alphabet (formal languages)

In

${\displaystyle \{v_{1},v_{2},\ldots \}}$

${\displaystyle \{v_{x}:x\in \mathbb {R} \}}$

If L is a formal language, i.e. a (possibly infinite) set of finite-length strings, the alphabet of L is the set of all symbols that may occur in any string in L. For example, if L is the set of all variable identifiers in the programming language C, L's alphabet is the set { a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _ }.

Given an alphabet ${\displaystyle \Sigma }$, the set of all strings of length ${\displaystyle n}$ over the alphabet ${\displaystyle \Sigma }$ is indicated by ${\displaystyle \Sigma ^{n}}$. The set ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ of all finite strings (regardless of their length) is indicated by the Kleene star operator as ${\displaystyle \Sigma ^{*}}$, and is also called the Kleene closure of ${\displaystyle \Sigma }$. The notation ${\displaystyle \Sigma ^{\omega }}$ indicates the set of all infinite sequences over the alphabet ${\displaystyle \Sigma }$, and ${\displaystyle \Sigma ^{\infty }}$ indicates the set ${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$ of all finite or infinite sequences.

For example, using the binary alphabet {0,1}, the strings ε, 0, 1, 00, 01, 10, 11, 000, etc. are all in the Kleene closure of the alphabet (where ε represents the empty string).

Applications

Alphabets are important in the use of

• Combinatorics on words
• Terminal and nonterminal symbols

References