Alphabet (formal languages)

By definition, the alphabet of a formal language L over \Sigma is the set \Sigma, which can be any non-empty set of symbols from which every string in L is built. For example, the set \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 L that means "all variable identifiers in the C programming language". It is not required to use every symbol in the alphabet of L for its strings. Given an alphabet \Sigma, the set of all strings of length n over the alphabet \Sigma is indicated by \Sigma^n. The set \bigcup_{i \in \mathbb{N}} \Sigma^i of all finite strings (regardless of their length) is indicated by the Kleene star operator as \Sigma^*, and is also called the Kleene closure of \Sigma. The notation \Sigma^\omega indicates the set of all infinite sequences over the alphabet \Sigma, and \Sigma^\infty indicates the set \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 formal languages, automata and semiautomata. In most cases, for defining instances of automata, such as deterministic finite automata (DFAs), it is required to specify an alphabet from which the input strings for the automaton are built. In these applications, an alphabet is usually required to be a finite set, but is not otherwise restricted. When using automata, regular expressions, or formal grammars as part of string-processing algorithms, the alphabet may be assumed to be the character set of the text to be processed by these algorithms, or a subset of allowable characters from the character set. ==See also==

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. .