Foundations: Alphabets, Strings & Languages

an alphabet

/ Sigma is written with the Greek capital letter Σ /

An alphabet is simply the set of building blocks you are allowed to use, like the tiles in a Scrabble box. Before you can talk about words, you must first agree on which letters exist. In English the building blocks are the 26 letters; for a digital signal they might be just 0 and 1; for DNA they are A, C, G, T. The alphabet fixes the raw material, and everything else (strings, languages, machines) is built on top of it.

Formally an alphabet is a finite, non-empty set of symbols, and by tradition we name it with the Greek capital letter Σ (Sigma). Two common examples are the binary alphabet Σ = {0, 1} and a tiny letter alphabet Σ = {a, b}. The two requirements matter: finite means there are only finitely many symbols (you cannot have infinitely many different letters), and non-empty means there is at least one symbol (with no symbols you could never write anything). What a symbol looks like is irrelevant; only that the symbols are distinct from one another.

Choosing the alphabet is the very first design decision in any problem. It is also where a subtle point lives: the symbols of Σ are treated as indivisible atoms. The two-character sequence 01 is not a symbol of {0, 1}; it is a string of two symbols. Keeping the line between a single symbol and a string of symbols sharp will save you from many beginner confusions later.

Σ = {a, b} is an alphabet with two symbols. Σ = {0, 1, 2, ..., 9} is the decimal alphabet. The empty set {} is NOT a valid alphabet (it must be non-empty).

An alphabet is finite and non-empty; its members are the atomic symbols.

Σ must be finite. An infinite set of symbols is not an alphabet in this theory; everything from strings to machines relies on having only finitely many distinct symbols.

Also called
Sigmasymbol set符號集Σ