Alphabet (Informatik)
aus Wikipedia, der freien Enzyklopädie
Ein Alphabet (altgriechisch ἀλφάβητος [alphábētos], sinngemäß das ABC) ist in der Theoretischen Informatik eine geordnete Menge von Zeichen.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Ein Alphabet ist nach DIN 44300 eine total geordnete endliche Menge von unterscheidbaren Symbolen.
[Bearbeiten] Schreibweise
Alphabete werden meist mit dem Formelzeichen Σ (Sigma) bezeichnet, seltener findet sich jedoch auch das Formelzeichen V (V) als Abkürzung des englischen vocabulary.
[Bearbeiten] Merkmale
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.
[Bearbeiten] 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.
