Alphabet (computer science)

# Alphabet (computer science)

Discussion
 Ask a question about 'Alphabet (computer science)' Start a new discussion about 'Alphabet (computer science)' Answer questions from other users Full Discussion Forum

Encyclopedia
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

and mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

, an alphabet is a non-empty set of symbol
Symbol
A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...

s
or letters, e.g. characters or digits. The most common alphabet is {0,1}, the binary alphabet. A finite string
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

is a finite sequence of letters from an alphabet; for instance a binary string is a string drawn from the alphabet {0,1}. An infinite sequence of letters may be constructed from elements of an alphabet as well.

Given an alphabet , we write to denote the set of all finite strings over the alphabet . Here, the denotes the Kleene star
Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...

operator. We write (or occasionally, or ) to denote the set of all infinite sequences over the alphabet .

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
Empty string
In computer science and formal language theory, the empty string is the unique string of length zero. It is denoted with λ or sometimes Λ or ε....

)

Alphabets are important in the use of formal languages, automata
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...

and semiautomata
Semiautomaton
In mathematics and theoretical computer science, a semiautomaton is an automaton having only an input, and no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function.Associated to any semiautomaton is a monoid called...

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