Alphabet (Informatik)

aus Wikipedia, der freien Enzyklopädie

In der Informatik und der mathematischen Logik ist ein Alphabet eine endliche Menge voneinander unterscheidbarer Symbole, die auch Zeichen oder Buchstaben genannt werden.

Alphabete werden oft mit dem Formelzeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} (Sigma) bezeichnet, seltener wird als Formelzeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} als Abkürzung für Vokabular (englisch

vocabulary

) benutzt.[1] Sie stellen 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.[2]

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.[3][4][5][6] Dieser Definition zufolge ist das Alphabet ein Zeichenvorrat, gleichbedeutend mit einem Zeichensatz.[7] 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 ,[8][9] siehe auch Lexikographische Ordnung.

Ein Wort ist eine endliche Folge von Symbolen eines Alphabets. Die Kleenesche Hülle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^*} des Alphabets bezeichnet die Menge aller Wörter über dem Alphabet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} , die durch Symbole aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} gebildet werden können. (Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^\omega} werden die abzählbar unendlichen Folgen von Zeichen aus dem Alphabet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} bezeichnet, siehe: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} = Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \aleph_0} . bezeichnet die gesamte Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^\ast \cup \Sigma^\omega} der endlichen Sequenzen und unendlichen Folgen von Zeichen.)

Die zu jedem Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^*} eindeutig bestimmte Zahl mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \in \Sigma^n} heißt Länge des Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} . Operationen auf Wörtern sind die Konkatenation (Verkettung), Potenz (mehrfach hintereinander Setzen), Spiegelung.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma = \{\mathit{do}, \mathit{re}, \mathit{mi}\}} ein Alphabet mit drei Elementen. Sie können in beliebiger Reihenfolge zusammenfügt werden, etwa zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle cdfg} ein Wort.

Beispiele

  • Mit Hilfe des Alphabets Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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 Zahlendarstellungen unterschieden. Eine Zahl ist dann ein Abstraktum, nämlich die Bedeutung (Semantik, hier: Zahlenwert) einer syntaktisch korrekten Zahlendarstellung.
  • Das römische Zahlensystem basiert in der Grundform auf dem Alphabet Σ = {I, V, X, L, C, D, M} (mit verschiedenen Erweiterungen für große Zahlen). 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. Die Zeichenfolgen 13 und XIII sind verschiedene Darstellungen derselben (abstrakten) Zahl.
  • 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_{D} = \{ dit, dah \}} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ .,- \}} , aus dem die Menge der Morsezeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_D} auf Grundlage der einzelnen Buchstabenhäufigkeiten gebildet wird. Neben den Buchstaben und Zahlen ist unter anderem auch SOS (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ...---...} ) direkt ein Morsezeichen, da es ohne Pause zwischen den dit und dah gemorst wird. Die Zeichen einer Nachricht werden - abgesehen von dieser Ausnahme - im Allgemeinen aber nicht einfach hintereinanderweg gemorst, sondern es wird zwischen den einzelnen Zeichen jeweils eine kurze Pause eingelegt. Dies ist nötig, da einige Zeichen ebenfalls den Anfang anderer Zeichen bilden; siehe Präfixcode. Das Morsealphabet selbst besteht also insgesamt aus den Zeichen und der Pause zwischen den Zeichen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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.

Das Alphabet einer Prädikatenlogik erster Stufe

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.

Definition eines Alphabet einer Prädikatenlogik erster Stufe

Das Alphabet einer Prädikatenlogik erster Stufe umfasst die folgenden Zeichen:[10]

  1.  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_0, v_1, v_2, \ldots \ -}   Variablenbezeichner;
  2.  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \neg, \wedge, \vee, \rightarrow, \leftrightarrow \ -}   Junktoren: Negation (nicht), Konjunktion (und), Disjunktion (oder), Implikation (wenn - dann), Äquivalenz (genau dann wenn);
  3.  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall, \exists \ -}   universaler und existenzieller Quantor;
  4.  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv \ -}   Gleichheitszeichen;
  5.  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ),(,\boldsymbol{,} \ -}   technische Zeichen: Klammersymbole und Komma;
  6.  des Weiteren
a)  eine (eventuell leere) Menge von Konstantensymbolen;
b)  für jedes n Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ge} 0 eine (eventuell leere) Menge von n-stelligen Relationssymbolen;
c)  für jedes n Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ge} 0 eine (eventuell leere) Menge von n-stelligen Funktionssymbolen.

Sei A die Menge der in (1) bis (5) aufgelisteten Symbole und S die Symbole aus (6). Dann bezeichne AS die Vereinigung von A und S. Man nennt AS das Alphabet der Prädikatenlogik erster Stufe und S seine Symbolmenge. Um das Alphabet einer Prädikatenlogik erster Stufe anzugeben, ist es ausreichend seine Symbolmenge anzugeben.

Manchmal verzichtet man in einem Alphabet auf das Gleichheitszeichen. In diesem Fall muss die Symbolmenge zumindest ein Relationssymbol enthalten, da ansonsten keine Formeln gebildet werden können.

Beispiel

Die wichtigste Prädikatenlogik erster Stufe, die Sprache der Mengenlehre, enthält nur ein einziges Zeichen in der Symbolmenge ihres Alphabets, nämlich das zweistellige Relationssymbol Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \in} (siehe Menge (Mathematik)).

Einzelnachweise und Bemerkungen

  1. ↑ Im Zusammenhang mit einer formalen Grammatik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} und der durch sie erzeugten formalen Sprache Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G)} wird der Zeichensatz der formalen Sprache Terminalalphabet genannt und oft mit dem Zeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} (statt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} ) bezeichnet. Darüber hinaus benötigt eine formale Grammatik noch eine davon disjunkte, nichtleere Menge von Nichtterminalen(Variablen), oft mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} (seltener mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} ) bezeichnet, formal handelt es sich dabei ebenfalls um ein Alphabet. Nichtterminale dürfen in Wörtern aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G)} nicht vorkommen. Die (disjunkte) Vereinigung von Terminalen und Nichtterminalen ist dann das gesamte Vokabular, oft mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} (oder eben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} ) bezeichnet.
  2. ↑ 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)
  3. ↑ Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 27.
  4. ↑ 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).
  5. ↑ 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).
  6. ↑ 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).
  7. ↑ 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).
  8. ↑ 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).
  9. ↑ 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).
  10. ↑ Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4, S. 13.
Abgerufen von „https://de.wikiup.org/index.php?title=Alphabet_(Informatik)&oldid=225031261“