Alphabet (computer science)

This article is about what computer scientists see as an alphabet. There is an article about alphabets (as a writing system) at alphabet

In computer science, an alphabet is a set of symbols (letters or digits are examples of symbols). It is like listing all the letters that can be used to make a word. Each symbol is only listed once. An alphabet has a finite number of symbols. That means you can finish writing down every symbol in an alphabet.

The most common alphabet in computer science is {0,1}. It is called the binary alphabet, because it contains two elements: 0 and 1. A finite string is a finite sequence of symbols from an alphabet. A binary string is a string made from the alphabet {0,1}, for example. An infinite sequence of symbols may be constructed from elements of an alphabet as well.

Given an alphabet $\Sigma$, we write $\Sigma^*$ to denote the set of all finite strings over the alphabet $\Sigma$. Here, the ${}^*$ denotes the Kleene star operator. We write $\Sigma^\infty$ (or occasionally, $\Sigma^\N$ or $\Sigma^\omega$) to denote the set of all infinite sequences over the alphabet $\Sigma$.

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

Alphabets are important in the use of formal languages and automatons. Automatons such as Deterministic Finite Automatons (DFAs) require an alphabet in the formal definition. All states in a DFA must have a transition on every element in an alphabet.

Other pages

• Formal language
• Syntax
• Semantics

References

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