Alphabet

Alphabet link

In formal language and coding theory, an alphabet is simply a finite, non-empty set of symbols from which we build strings. Formally:

• We denote an alphabet by a capital Greek letter, most often $\Sigma$ (capital sigma).
• Each element of $\Sigma$ is called a symbol or character.
• By “finite” we mean $\Sigma$ contains a limited number of symbols (so you can actually list them all).
• By “non-empty” we mean $\Sigma$ must have at least one symbol.

Examples link

• $\Sigma = \lbrace 0,1 \rbrace $ - the binary alphabet.
• $\Sigma = \lbrace a,b,…,z \rbrace $ - the lowercase English alphabet.
• $\Sigma = \lbrace A,…,Z,a,…,z,0,…,9 \rbrace $ - alphabet of alphanumeric characters.

Kleene star of Σ link

In formal language theory, given an alphabet $\Sigma$:

$$ \Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k $$

is the Kleene star of $\Sigma$, i.e. the set of all finite strings (including the empty string) you can form using symbols from $\Sigma$. Concretely:

• $\Sigma^0 = \lbrace \emptyset \rbrace$, where $\emptyset$ is the empty string.
• $\Sigma^1 = \lbrace \Sigma \rbrace$
• $\Sigma^2 = \lbrace ab \mid a, b \in \Sigma \rbrace$
• And so on, up to $\Sigma^k$ for any non-negative integer $k$.

Hence

$$ \Sigma^* = \lbrace \emptyset \rbrace \cup \Sigma \cup \Sigma^2 \cup \Sigma^3 \cup … $$

Examples link

If $\Sigma = \lbrace 0,1 \rbrace$, then

$$ \Sigma^* = \lbrace \emptyset,0,1,00,01,10,11,000,… \rbrace $$