In informatica, l'alfabeto è un insieme finito non vuoto. Gli elementi di un alfabeto sono chiamati lettere o simboli dell'alfabeto.
Esempi di alfabeti
Un esempio semplice di alfabeto è { - , ⋅ ⋅ } 
, dove i simboli «-» (trattino) e «·» (punto) possono essere usati per il codice Morse. In altri contesti, come nei linguaggi di programmazione, elementi dell'alfabeto possono essere parole chiave o token come se, altrimenti, per, mentre (parole che individuano costrutti sintattici). Un insieme infinito, ad esempio l'insieme dei numeri naturali, non è un alfabeto perché non è finito.
Alfabeto binario e stringhe
L'alfabeto più comune in informatica è {0,1}. È chiamato alfabeto binario perché contiene due simboli. Un alfabeto viene usato per costruire stringhe (o parole): una stringa è una sequenza finita di lettere dell'alfabeto. Ad esempio, una stringa di lunghezza 5 su {0,1} è 01101. Per una stringa w denotiamo la sua lunghezza con |w|; per esempio |01101| = 5.
La stringa vuota è la stringa che non contiene lettere; spesso è indicata con la lettera greca lambda, λ {\displaystyle \lambda } 
. La stringa vuota è una stringa valida su qualsiasi alfabeto e la sua lunghezza è zero: |λ| = 0.
La stella di Kleene (χiusura di Kleene)
Se abbiamo un alfabeto chiamato Σ {\i} 
, si indica con l'insieme di tutte le stringhe che possono essere formate con i simboli di Σ e con l'operazione di concatenazione. L'insieme di tutte le stringhe di lunghezza arbitraria (compresa la stringa vuota) è chiamato la stella di Kleene o chiusura di Kleene di Σ, e si denota con Σ 
. Il termine prende il nome dal matematico Stephen Cole Kleene.
Esplicitamente, Σ* = {λ, tutte le stringhe di lunghezza 1 su Σ, tutte le stringhe di lunghezza 2 su Σ, tutte le stringhe di lunghezza 3 su Σ, ...}. Per l'alfabeto binario questo dà ad esempio la seguente lista (in stile di enumerazione): { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . } 
. I puntini indicano che Σ* è infinito e non può essere elencato per intero.
Notazioni e operazioni
- Concatenazione: se x e y sono stringhe su Σ, la loro concatenazione si indica con xy. Ad esempio, concat(01, 10) = 0110.
- Potenza: Σn indica l'insieme di tutte le stringhe di lunghezza n su Σ. In particolare Σ0 = {λ}.
- Stella di Kleene: Σ* = ⋃n≥0 Σn. Esiste anche la più di Kleene Σ+ = ⋃n≥1 Σn = Σ* \ {λ}.
- Linguaggio: un linguaggio su Σ è qualsiasi sottoinsieme di Σ*. Le operazioni classiche sui linguaggi includono unione, intersezione, concatenazione e chiusura di Kleene.
Perché gli alfabeti sono utili
Gli alfabeti e la loro chiusura servono come base per lo studio dei linguaggi formali, degli automi finiti, delle espressioni regolari e della teoria della computazione. Permettono di modellare e analizzare:
- i linguaggi riconosciuti da macchine astratte (automi deterministici e non deterministici);
- le proprietà decidibili o meno di problemi di riconoscimento e trasformazione di stringhe;
- la rappresentazione dell'informazione (ad esempio codifiche binarie come ASCII o Unicode sono basate su alfabeti finiti di bit o di symboli).
In sintesi, un alfabeto è l'insieme finito di simboli di base che, mediante concatenazione, genera uno spazio di stringhe (Σ*) su cui si definiscono linguaggi, macchine e problemi fondamentali dell'informatica.