Alphabet (computer science)

In computer science, an alphabet is a finite non-empty set. The elements of an alphabet are called the letters or symbols of the alphabet.

An example of an alphabet is ${\displaystyle \{-,\cdot \}}$ which may be used for Morse code or {begin, if, else, for, while} which may be the keywords of a Programming language.

The set of natural numbers is not an alphabet because as it is not finite.

The alphabet which is used the most in computer science is {0,1}. It is called the binary alphabet because it contains two symbols. An alphabet can be used to make a string (or word). This is a finite Sequence of letters from the alphabet. For example, a string of length 5 over {0,1} is 01101.

The empty string is the string containing no letters (it is often written as ${\displaystyle \lambda }$). The empty string is a string over any alphabet.

If we have an alphabet called ${\displaystyle \Sigma }$, then we write the set of all strings that can be made from ${\displaystyle \Sigma }$ as ${\displaystyle \Sigma ^{*}}$. This is called the Kleene star (or Kleene closure) of ${\displaystyle \Sigma }$. It is named after the mathematician Stephen Cole Kleene.

The Kleene star of the binary alphabet is ${\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}}$. The three dots after 001, show that we cannot write the Kleene star of an alphabet in full because it is an infinite set.

Alphabets are important because they are used in studying formal languages, finite automata and very difficult questions in computer science about what can be computed and what can not.