Alfabet (matematik)

Inom datavetenskap och matematisk logik kallas en ändlig och icke tom mängd för alfabet när avsikten är att använda den för strängoperationer. Mängdens element kallas då ofta "tecken", exempelvis siffror, bokstäver. Ett vanligt alfabet är till exempel det binära alfabetet {0,1} eller det svenska alfabetet {a, ..., ö, A, ..., Ö}. En ändlig sträng är en ändlig följd (sekvens) av bokstäver från alfabetet - exempelvis är en binär sträng en sekvens av ettor och nollor från alfabetet {0,1}. Även oändliga strängar kan bildas från alfabetet.

Om vi har ett alfabet, vanligen betecknat $\Sigma$, skriver vi $\Sigma ^{*}$ för att betckna mängden av alla ändliga strängar över alfabetet $\Sigma$. Här betecknar ${}^{*}$ operatorn Kleenestjärna, så $\Sigma ^{*}$ kallas också Kleenehöljet till $\Sigma$. Man skriver $\Sigma ^{\infty }$ (även $\Sigma ^{\mathbb {N} }$ eller $\Sigma ^{\omega }$) för att beteckna mängden av alla oändliga strängar över $\Sigma$.

Exempelvis, om vi använder det binära alfabetet {0,1}, ingår alla strängarna ε, 0, 1, 00, 01, 10, 11, 000, etc. i alfabetets Kleenehölje {0,1}* (där ε betecknar den tomma strängen).

Alfabeten är viktiga inom formella språk och automatteori.

Referenser

• Marco Kuhlmann, 2013, Kompendium till kursen Matematik för språkteknologer, Uppsala universitet, kapitel 6.
• Mats Dahllof, Strängarnas matematik.
• Tao Jiang, Ming Li, Bala Ravikumar, Kenneth W. Regan, Formal Grammars and Languages, kapitel 1, i Mikhail J. Atallah (red.), 1999, Algorithms and theory of computation handbook, ISBN 0-8493-2649-4, CRC Press LLC.