Alphabet

Unter einem Alphabet A versteht man eine nichtleere Menge von Zeichen bzw. Symbolen. Alphabete sind ein zentraler Begriff der theoretischen Informatik und sind die Grundbausteine von Wörtern, die wiederum die Bausteine von Sprachen bilden. Der zentrale Bestandteil einer Logik ist deren zugrundeliegende Sprache. Das Alphabet dieser Sprache gibt dann die Menge der zulässigen Zeichen an, die benutzt werden dürfen, um die Terme und Ausdrücke dieser Logik aufzubauen. Endliche lineare Reihen von Zeichen eines Alphabets heißen Zeichenreihen oder Wörter über A. Die Menge der Wörter wird mit A* bezeichnet. Auch die Zeichenreihe, die keine Symbole enthält, ist ein Wort – das leere Wort. Es wird mit \varepsilon bezeichnet.

Alphabete werden oft mit dem Formelzeichen \Sigma (Sigma) bezeichnet, seltener wird als Formelzeichen V als Abkürzung für Vokabular (englisch vocabulary) benutzt.[1] Die Kleenesche Hülle \Sigma ^{*} des Alphabets bezeichnet die Menge aller Wörter (d. h. endlichen Sequenzen) über dem Alphabet \Sigma , die durch Symbole aus \Sigma gebildet werden können. Formal ist diese gegeben durch die disjunkte Vereinigung

{\displaystyle \Sigma ^{*}=\bigcup _{n\in \mathbb {N} \cup \{0\}}\Sigma ^{n}}  .

(Mit \Sigma ^{\omega } werden die abzählbar unendlichen Folgen von Zeichen aus den Alphabet \Sigma bezeichnet, siehe: \omega = \aleph _{0}. {\displaystyle \Sigma ^{\infty }} bezeichnet die gesamte Menge {\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }} der endlichen Sequenzen und unendlichen Folgen von Zeichen.)

Die zu jedem Wort w aus \Sigma ^{*} eindeutig bestimmte Zahl n mit {\displaystyle w\in \Sigma ^{n}} heißt Länge des Wortes w. Operationen auf Wörtern sind die Konkatenation (Verkettung), Potenz (mehrfach hintereinander Setzen), Spiegelung; ein Wort kann Teil eines anderen Wortes sein (Infix, englisch substring) – näheres siehe Wort (Theoretische Informatik): Alphabete stellen somit das Zeicheninventar für Wörter zur Verfügung und bilden damit die Grundlage für formale Sprachen.

Man muss unterscheiden zwischen dem Alphabet aus Einzelzeichen und den Wörtern unterschiedlicher Länge, die über diesem Alphabet gebildet werden. Insbesondere gehört das leere Wort (das triviale Wort mit der Länge 0) nie zum Alphabet, da es in jeder Wortmenge enthalten ist. Menge der nicht-leeren Worte:

{\displaystyle \Sigma ^{+}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}}  .

Definition

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. Dieser Definition zufolge ist das Alphabet ein Zeichenvorrat, gleichbedeutend mit einem Zeichensatz. 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 {\displaystyle (\Sigma ,\leq )}.

Abgrenzung zur natürlichen Sprache

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 {\displaystyle \color {black}{\mathit {do}}\color {red}{\mathit {mi}}\color {black}{\mathit {do}}\color {red}{\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 {\displaystyle \color {black}{\mathit {do}}\color {red}{\mathit {mi}}\color {black}{\mathit {do}}\color {red}{\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. In vielen Computersprachen ist dafür die englische Bezeichnung string im Gebrauch. Auch über dem lateinischen Alphabet ist also in der Informatik die Zeichenfolge cdfg ein Wort.

Beispiele

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

Anmerkungen

  1. Im Zusammenhang mit einer formalen Grammatik G und der durch sie erzeugten formalen Sprache L(G) wird der Zeichensatz der formalen Sprache Terminalalphabet genannt und oft mit dem Zeichen T (statt \Sigma ) bezeichnet. Darüber hinaus benötigt eine formale Grammatik noch eine davon disjunkte, nichtleere Menge von Nichtterminalen(Variablen), oft mit N (seltener mit <V) bezeichnet, formal handelt es sich dabei ebenfalls um ein Alphabet. Nichtterminale dürfen in Wörtern aus L(G) nicht vorkommen. Die (disjunkte) Vereinigung von Terminalen und Nichtterminalen ist dann das gesamte Vokabular, oft mit V (oder eben \Sigma ) bezeichnet.
Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 23.11. 2022