Alphabet (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Alphabet (Informatik), Zeichensatz und Zeichenkodierung überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Zahnradzacken 19:27, 23. Dez. 2011 (CET)

In der Informatik ist ein Alphabet eine endliche Menge von voneinander unterscheidbaren Symbolen, die auch Zeichen oder Buchstaben genannt werden.

Alphabete werden oft mit dem Formelzeichen \Sigma (Sigma) bezeichnet, seltener wird als Formelzeichen V als Abkürzung des englischen vocabulary benutzt. Die Kleenesche Hülle \Sigma^* des Alphabets bezeichnet die Menge aller Wörter über dem Alphabet \Sigma, die durch Symbole aus \Sigma 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.

In einem Alphabet kommen keine Wörter vor, die über diesem Alphabet gebildet werden. Insbesondere gehört das leere Wort nie zum Alphabet, da es in jeder Wortmenge enthalten ist.[1]

Definition[Bearbeiten]

Ein Alphabet ist eine endliche Menge. Oft wird auch verlangt, dass die Menge nicht leer ist. Die Elemente eines Alphabets werden als Buchstaben, Symbole oder Zeichen bezeichnet.[2][3][4][5] Dieser Definition zufolge ist das Alphabet ein Zeichenvorrat, gleichbedeutend mit einem Zeichensatz.[6] Mit dem Wort Zeichensatz ist aber oft auch eine Zeichenkodierung gemeint. Alphabete sind hingegen unabhängig von einer Kodierung.

Nach DIN 44300 ist ein Alphabet dagegen eine total geordnete endliche Menge von unterscheidbaren Symbolen. Es handelt sich demnach genauer gesagt um einen Zeichenvorrat zusammen mit einer Totalordnung.[7][8]

Abgrenzung zur natürlichen Sprache[Bearbeiten]

In der Informatik ist das Alphabet eine Verallgemeinerung der üblichen Alphabete natürlicher Sprachen. Beispielsweise ist das Alphabet der lateinischen Buchstaben auch ein Alphabet im Sinne der Informatik. In der Theoretischen Informatik kommen jedoch häufig auch Alphabete vor, deren Elemente Symbole sind, die man mit mehreren Buchstaben darstellt. Zum Beispiel ist \Sigma = \{\mathit{do}, \mathit{re}, \mathit{mi}\} ein Alphabet mit drei Elementen. Sie können in beliebiger Reihenfolge zusammenfügt werden, etwa zu \mathit{do} \mathit{mi} \mathit{do} \mathit{re}.

Hier ist dann die Arbitrarität der Symbole besonders wichtig: Welche Zeichen für die Elemente des Alphabets verwendet werden, ist belanglos, solange sie voneinander unterscheidbar sind. Die Zeichenkette \mathit{do} \mathit{mi} \mathit{do} \mathit{re} kann also beispielsweise für eine Tonfolge stehen, aber genauso auch für eine Programmsteuerung mit drei unterschiedlichen Befehlen.

In dem Zusammenhang ist auch zu beachten, dass man in der Informatik jede beliebige Folge von Zeichen eines Alphabets als Wort bezeichnet. Auch über dem lateinischen Alphabet ist also in der Informatik die Zeichenfolge cdfg ein Wort.

Beispiele[Bearbeiten]

  • Mit Hilfe des Alphabets \Sigma = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \rbrace 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 \Sigma_{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 (da einige Zeichen ebenfalls Anfang anderer Zeichen sind, wird dies nötig; siehe Präfixcode). Das Morsealphabet selbst besteht also aus den Zeichen und der Pause zwischen den Zeichen:  \Sigma_{M} = L_D \cup \{ \text{PAUSE} \}.

Diese Beispiele sollen verdeutlichen, dass sich der Aufbau eines komplexen Kommunikationssystems durch gegebenenfalls hierarchisch aufgebaute Paare von Alphabeten und zugeordneten Sprachen beschreiben lässt.

Einzelnachweise[Bearbeiten]

  1. Christian Wagenknecht, Michael Hielscher: Formale Sprachen, abstrakte Automaten und Compiler: Lehr- und Arbeitsbuch für Grundstudium und Fortbildung. ISBN 3-8348-0624-2, S. 20. (online)
  2.  Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 27.
  3.  Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie (= Teubner Leitfäden der Informatik). 2. über. u. erw. Auflage. B.G. Teubner Verlag, 2004, ISBN 3-519-10332-X, S. 33 (eingeschränkte Vorschau in der Google-Buchsuche).
  4.  Susanna S. Epps: Discrete Mathematics with Applications. 4 Auflage. Brooks Cole Pub Co, 2010, ISBN 0-495-39132-8, S. 781 (eingeschränkte Vorschau in der Google-Buchsuche).
  5.  Alexandru Mateescu, Arto Salomaa: Formal Languages: an Introduction and a Synopsis. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of formal languages. Word, Language, Grammar. Vol. 1, Springer-Verlag, 1997, ISBN 3-540-60420-0, S. 10 (eingeschränkte Vorschau in der Google-Buchsuche).
  6.  Manfred Broy: Systemstrukturen und Theoretische Informatik. In: Informatik. Eine grundlegende Einführung. 2. überarb. Auflage. Band 2, Springer, Berlin 1998, ISBN 3-540-64392-3, S. 191 (eingeschränkte Vorschau in der Google-Buchsuche).
  7.  Hans-Jürgen Appelrath, Jochen Ludewig: Skriptum Informatik. Eine konventionelle Einführung. 5 Auflage. B.G. Teubner, Stuttgart/ Leipzig 2000, ISBN 3-519-42153-4, S. 24 (eingeschränkte Vorschau in der Google-Buchsuche).
  8.  Gerhard Goos, Friedrich L. Bauer: Informatik 1. Eine einführende Übersicht. 4. verb. Auflage. Springer, Berlin/ Heidelberg 1991, ISBN 3-540-52790-7, S. 29 (eingeschränkte Vorschau in der Google-Buchsuche).