Alphabet (Informatik)
Für andere Bedeutungen von „Alphabet“ siehe Alphabet (Begriffsklärung).
Ein Alphabet (sächlich, griechisch αλφάβητο, alfáwito - sinngemäß das ABC) bezeichnet (nach DIN 44300) in der theoretischen Informatik eine total geordnete endliche Menge von unterscheidbaren Symbolen (Zeichen). Für Alphabete wird häufig Σ als Formelzeichen verwendet.
Man kann sich ein Alphabet wie ein normales Alphabet vorstellen, beispielsweise das Alphabet der lateinischen Buchstaben. In der Informatik kommen jedoch häufig auch Alphabete vor, deren Zeichen bereits aus mehreren Buchstaben bestehen, beispielsweise: Σ = {oma, mutter, tochter}. Hier ist dann die Arbitrarität der Symbole besonders wichtig: welches Zeichen für die Elemente des Alphabets verwendet werden ist belanglos, solange sie voneinander unterscheidbar sind.
Die Kleenesche Hülle Σ* des Alphabets bezeichnet die Menge aller Wörter über dem Alphabet Σ. Alphabete bilden somit die Grundlage für formale Sprachen, deren Zeicheninventar für Wörter sie zur Verfügung stellen. Entscheidbare Sprachen lassen sich durch formale Grammatiken darstellen, bei denen zwischen terminalen und nicht-terminalen (auch: non-terminalen) Symbolen unterschieden wird. Non-Terminale dürfen dabei nicht in Wörtern der Sprache vorkommen, sondern müssen zunächst durch Regeln der Grammatik gegen andere (terminale) Symbole ersetzt werden.
Beispiele
- Dezimalzahlensystem: Es ist Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } und alle Wörter über Σ können als Dezimalzahlen aufgefasst werden (zumindest wenn führende Nullen erlaubt sein sollen). In der Zahlenlehre wird entsprechend der Unterscheidung von Zeichen eines Alphabets und Wörtern über diesem Alphabet zwischen Ziffern und Zahlen unterschieden.
- römisches Zahlensystem: Σ = {I, V, X, L, C, D, M}, wobei hier die Regeln, wie die Zeichenfolge beschaffen sein muss um als "Wort" des römischen Zahlensystems zu gelten komplex sind (IV anstatt IIII, größere Einheiten weiter links als kleinere, ...) aber sich immerhin mithilfe einer formalen Sprache darstellen lassen.
- Morsecode: Für den Morsecode lassen sich zwei unterschiedliche Alphabete angeben, die das Kommunikationssystem des morsens auf unterschiedlichen Ebenen beschreiben: Zunächst ist das Alphabet Σditdah = {dit, dah} bzw. {., -}, aus dem die Menge der Morsezeichen Lditdah durch eine formale Sprache nach dem Ökonomieprinzip gebildet werden. Neben den Buchstaben und Zahlen ist unter anderem auch SOS (...---...) direkt ein Morsezeichen, da es ohne Pause zwischen den dit und dah gemorst wird.
Die Zeichen einer Nachricht werden nicht einfach hintereinanderweg gemorst, sondern zwischen den einzelnen Zeichen wird jeweils eine kurze Pause eingelegt (dies ist nötig da nicht alle Zeichen dieselbe Länge haben). Das Morsealphabet selbst besteht also aus den Zeichen und der Pause zwischen den Zeichen: Σmorse = Lditdah ∪ { PAUSE } .
Dieses Beispiel sollte verdeutlichen, dass sich der Aufbau eines komplexen Kommunikationssystems durch gegebenenfalls hierarchisch aufgebaute Paare von Alphabeten und zugeordneten Sprachen beschreiben lässt.