I datavetenskap är ett alfabet en ändlig icke-tom mängd. Elementen i ett alfabet kallas alfabetets bokstäver eller symboler. Ett alfabet får alltså inte vara tomt och måste ha ett ändligt antal symboler.
Exempel
Ett enkelt exempel på ett alfabet är { - , ⋅ } {\displaystyle \{-,\cdot \}}
, som kan användas för morsekod. Ett annat vanligt exempel är nyckelord i ett programmeringsspråk, t.ex. {begin, if, else, for, while}.
Mängden naturliga tal är inte ett alfabet eftersom den inte är ändlig.
Det alfabet som används mest inom datavetenskap är {0,1}. Det kallas det binära alfabetet eftersom det innehåller två symboler. Storleken på ett alfabet kallas ibland dess radix eller antal symboler, och betecknas |Σ| när alfabetet heter Σ {\displaystyle \Sigma } 
.
Strängar (ord) och tomma strängen
Ett alfabet används för att bilda en sträng (eller ett ord): en ändlig sekvens av bokstäver från alfabetet. Exempelvis är 01101 en sträng av längd 5 över {0,1}. Längden på en sträng w betecknas ofta |w|.
Den tomma strängen är den sträng som inte innehåller några bokstäver; den skrivs ofta som λ {\displaystyle \lambda } 
. Den tomma strängen tillhör Σ* för vilket alfabet Σ som helst.
Kleene-stjärnan och relaterade begrepp
Om vi har ett alfabet som heter Σ {\displaystyle \Sigma } skriver vi mängden av alla strängar som kan skapas från Σ {\displaystyle \Sigma } som Σ ∗ {\displaystyle \Sigma ^{*}} 
. Detta kallas Kleene-stjärnan (eller Kleene-avslutningen) för Σ {\displaystyle \Sigma } och är uppkallad efter matematikern Stephen Cole Kleene.
Konkret definieras Kleene-stjärnan som föreningen av Σ^n för alla n ≥ 0, där Σ^n är mängden av alla strängar av längd n över Σ. Man har särskilt Σ^0 = {λ {\displaystyle \lambda }} (den tomma strängen) och Σ^1 = Σ.
Kleene-stjärnan för det binära alfabetet är { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . } {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} 
. De tre prickarna efter 001 visar att mängden är oändlig och därför inte kan skrivas ut helt.
En nära besläktad konstruktion är Kleene-plustecknet Σ+ = ⋃_{n≥1} Σ^n, det vill säga mängden av alla icke-tomma strängar över Σ. Därför gäller Σ* = Σ+ ∪ {λ}.
Operationer och notationshjälp
- Konkatenering: Om u och v är strängar över samma alfabet är uv konkateneringen (förbindelsen) av u och v.
- Längd: |w| anger antalet symboler i strängen w. Exempel: |01101| = 5.
- Potens: Σ^n är mängden av alla strängar av längd n över Σ.
- Språk: En delmängd L ⊆ Σ* kallas ett formellt språk. Språk studeras i samband med ändliga automater, reguljära uttryck och grammatik.
Tillämpningar och betydelse
Alfabet spelar en grundläggande roll i teorin om formella språk, ändliga automater, kompileringsmetoder, reguljära uttryck, kodning och kommunikation (t.ex. felrättande koder och överföringsprotokoll). De används också för att formulera och analysera svåra frågor inom datavetenskap om vad som kan beräknas och vad som inte kan beräknas.
Sammanfattningsvis är ett alfabet en enkel men central byggsten i formell språk- och automatteori: en ändlig, icke-tom mängd symboler som används för att bilda strängar och språk. Genom operationer som konkatenering och Kleene-stjärnan kan man beskriva mycket komplexa (och ofta oändliga) mängder av strängar.