Alphabet (formal languages)

Strings, also known as "words" or "sentences", over an alphabet are defined as a sequence of the symbols from the alphabet set. For example, the alphabet of lowercase letters "a" through "z" can be used to form English words like "iceberg" while the alphabet of both upper and lower case letters can also be used to form proper names like "Wikipedia". A common alphabet is {0,1}, the binary alphabet, and "00101111" is an example of a binary string. Infinite sequences of symbols may be considered as well (see Omega language).

Strings are often written as the concatenation of their symbols, and when using this notational convention it is convenient for practical purposes to restrict the symbols in an alphabet so that this notation is unambiguous. For instance, if the two-member alphabet is {00,0}, a string written in concatenated form as "000" is ambiguous because it is unclear if it is a sequence of three "0" symbols, a "00" followed by a "0", or a "0" followed by a "00". However, this is a limitation on the notation for writing strings, not on their underlying definitions. Like any finite set, {00,0} can be used as an alphabet, whose strings can be written unambiguously in a different notational convention with commas separating their elements: 0,00 ≠ 0,0,0 ≠ 00,0.

Notation

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

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