Alphabet (formal languages)

In

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

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

By definition, the alphabet of a formal language ${\displaystyle L}$ over ${\displaystyle \Sigma }$ is the set ${\displaystyle \Sigma }$, which can be any non-empty set of symbols from which every string in ${\displaystyle L}$ is built. For example, the set ${\displaystyle \Sigma =\{\_,\mathrm {a} ,\dots ,\mathrm {z} ,\mathrm {A} ,\dots ,\mathrm {Z} ,0,\mathrm {1} ,\dots ,\mathrm {9} \}}$ can be the alphabet of the formal language ${\displaystyle L}$ that means "all variable identifiers in the C programming language". Notice that it is not required to use every symbol in the alphabet of ${\displaystyle L}$ for its strings.

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).

Alphabets are important in the use of

• Combinatorics on words
• Terminal and nonterminal symbols