Zeichenvorrat

Ein Alphabet ist in der Theoretischen Informatik eine endliche Menge von voneinander unterscheidbaren Symbolen, die auch Zeichen oder Buchstaben genannt werden. Alphabete werden meist mit dem Formelzeichen Σ (Sigma) bezeichnet, seltener wird als Formelzeichen V (V) als Abkürzung des englischen vocabulary benutzt. Die Kleenesche Hülle Σ ^* des Alphabets bezeichnet die Menge aller Wörter über dem Alphabet Σ, die durch Symbole aus Σ gebildet werden können. Alphabete stellen somit das Zeicheninventar für Wörter zur Verfügung und bilden damit die Grundlage für formale Sprachen.

Definition

Ein Alphabet ist nach DIN 44300 eine total geordnete endliche Menge von unterscheidbaren Symbolen.

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.

Beispiele

• Mit Hilfe des Alphabets Σ = {0,1,2,3,4,5,6,7,8,9} können alle natürlichen Zahlen im Dezimalsystem gebildet werden. In der Zahlenlehre wird entsprechend der Unterscheidung von Zeichen eines Alphabets und Wörtern über diesem Alphabet zwischen Ziffern und Zahlen unterschieden.
• Das römische Zahlensystem basiert auf dem Alphabet Σ = {I, V, X, L, C, D, M}. Hier sind jedoch die Regeln, wie die Zeichenfolge beschaffen sein muss, um als Wort des römischen Zahlensystems zu gelten, komplex (IV anstatt IIII, größere Einheiten weiter links als kleinere, ...). Sie können aber durch eine formale Grammatik dargestellt werden.
• Für den Morsecode lassen sich zwei unterschiedliche Alphabete angeben, die das Kommunikationssystem des Morsens auf unterschiedlichen Ebenen beschreiben: Zunächst gibt es das Alphabet Σ_D = {dit,dah} bzw. {., − }, aus dem die Menge der Morsezeichen L_D auf Grundlage der einzelnen Buchstabenhäufigkeiten gebildet wird. 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: $\Sigma_{M} = L_D \cup \{ \text{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.

Literatur

• Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 27.