imported>Hgzh: /* Abgrenzung zur natürlichen Sprache */ fix Darkmode

2026-02-01T11:48:12Z

Abgrenzung zur natürlichen Sprache: fix Darkmode

Neue Seite

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

Alphabete werden oft mit dem Formelzeichen <math>\Sigma</math> ([[Sigma]]) bezeichnet, seltener wird als Formelzeichen <math>V</math> als Abkürzung für ''Vokabular'' ([[Englische Sprache|englisch]] ''{{lang|en|vocabulary}}'') benutzt.<ref>Im Zusammenhang mit einer [[formale Grammatik|formalen Grammatik]] <math>G</math> und der durch sie erzeugten [[formale Sprache|formalen Sprache]] <math>L(G)</math> wird der Zeichensatz der formalen Sprache ''[[Terminalsymbol|Terminalalphabet]]'' genannt und oft mit dem Zeichen <math>T</math> (statt <math>\Sigma</math>) bezeichnet. Darüber hinaus benötigt eine formale Grammatik noch eine davon [[disjunkt]]e, nichtleere Menge von ''[[Nichtterminale]]n''(''Variablen''), oft mit <math>N</math> (seltener mit <math>V</math>) bezeichnet, formal handelt es sich dabei ebenfalls um ein Alphabet. Nichtterminale dürfen in Wörtern aus <math>L(G)</math> nicht vorkommen. Die (disjunkte) Vereinigung von Terminalen und Nichtterminalen ist dann das gesamte ''Vokabular'', oft mit <math>V</math> (oder eben <math>\Sigma</math>) bezeichnet.</ref> Sie stellen das Zeicheninventar für [[Wort (Theoretische Informatik)|Wörter]] zur Verfügung und bilden damit die Grundlage für [[formale Sprache]]n. Man muss unterscheiden zwischen dem Alphabet aus Einzelzeichen und den Wörtern unterschiedlicher Länge, die über diesem Alphabet gebildet werden.<ref>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. [https://books.google.de/books?id=mXlrWEexCbMC&pg=PA20&hl=de#v=onepage&q&f=false (online)]</ref>

== 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.<ref>{{Literatur|Autor=Katrin Erk, Lutz Priese|Titel=Theoretische Informatik: eine umfassende Einführung|Verlag=Springer-Verlag|Jahr=2002|Auflage=2., erw.|Seiten=27|ISBN=3-540-42624-8}}</ref><ref>{{Literatur|Autor=[[Juraj Hromkovič]]|Titel=Theoretische Informatik|TitelErg=Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie|Reihe=Teubner Leitfäden der Informatik|Jahr=2004|Verlag=B.G. Teubner Verlag|ISBN=3-519-10332-X|Auflage=2. über. u. erw.|Seiten=33|Online={{Google Buch|BuchID=HGCcxY9fHs8C|Seite=31}}}}</ref><ref>{{Literatur|Autor=Susanna S. Epps|Titel=Discrete Mathematics with Applications|Jahr=2010|Verlag=Brooks Cole Pub Co|ISBN=0-495-39132-8|Auflage=4|Seiten=781|Online={{Google Buch|BuchID=PPc_2qUhXrAC|Seite=781}}}}</ref><ref>{{Literatur|Herausgeber=Grzegorz Rozenberg, Arto Salomaa|Titel=Formal Languages: an Introduction and a Synopsis|Autor=Alexandru Mateescu, Arto Salomaa|Sammelwerk=Handbook of formal languages|WerkErg=Word, Language, Grammar|Band=Vol. 1|Jahr=1997|Verlag=Springer-Verlag|ISBN=3-540-60420-0|Seiten=10|Online={{Google Buch|BuchID=yQ59ojndUt4C|Seite=10}}}}</ref>
Dieser Definition zufolge ist das Alphabet ein Zeichenvorrat, gleichbedeutend mit einem [[Zeichensatz]].<ref>{{Literatur|Autor=[[Manfred Broy]]|Titel=Systemstrukturen und Theoretische Informatik|Band=Band 2|Sammelwerk=Informatik|WerkErg=Eine grundlegende Einführung|Jahr=1998|Verlag=Springer|Ort=Berlin|ISBN=3-540-64392-3|Auflage=2. überarb.|Seiten=191|Online={{Google Buch|BuchID=6RzKvw5s0QcC|Seite=191}}}}</ref> 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 [[Totalordnung|total geordnete]] endliche Menge von unterscheidbaren Symbolen. Es handelt sich demnach genauer gesagt um einen Zeichenvorrat zusammen mit einer [[Ordnungsrelation#Totalordnung|Totalordnung]] <math>(\Sigma,\le)</math>,<ref>{{Literatur|Autor=Hans-Jürgen Appelrath, Jochen Ludewig|Titel=Skriptum Informatik|TitelErg=Eine konventionelle Einführung|Jahr=2000|Verlag=B.G. Teubner|Ort=Stuttgart/Leipzig|ISBN=3-519-42153-4|Auflage=5|Seiten=24|Online={{Google Buch|BuchID=qZgCknBY93QC|Seite=24}}}}</ref><ref>{{Literatur|Autor=Gerhard Goos, Friedrich L. Bauer|Titel=Informatik 1|TitelErg=Eine einführende Übersicht|Jahr=1991|Verlag=Springer|Ort=Berlin/Heidelberg|ISBN=3-540-52790-7|Auflage=4. verb.|Seiten=29|Online={{Google Buch|BuchID=iFFIjepxKAYC|Seite=29}}}}</ref> siehe auch [[Lexikographische Ordnung]].

Ein [[Wort (theoretische Informatik)|Wort]] ist eine endliche Folge von Symbolen eines Alphabets. Die [[Kleenesche Hülle]] <math>\Sigma^*</math> des Alphabets bezeichnet die Menge aller Wörter über dem Alphabet <math>\Sigma</math>, die durch Symbole aus <math>\Sigma</math> gebildet werden können. (Mit <math>\Sigma^\omega</math> werden die abzählbar ''unendlichen'' Folgen von Zeichen aus dem Alphabet <math>\Sigma</math> bezeichnet, siehe: [[Ordinalzahl#Die natürlichen Zahlen als geordnete Mengen|<math>\omega</math>]] = [[Kardinalzahl (Mathematik)#Schreibweise|<math>\aleph_0</math>]]. <math>\Sigma^\infty</math> bezeichnet die gesamte Menge <math>\Sigma^\ast \cup \Sigma^\omega</math> der endlichen Sequenzen und unendlichen Folgen von Zeichen.)

Die zu jedem Wort <math>w</math> aus <math>\Sigma^*</math> eindeutig bestimmte Zahl <math>n</math> mit <math>w \in \Sigma^n</math> heißt ''Länge'' des Wortes <math>w</math>. 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 [[Alphabet]]e [[Natürliche Sprache|natürlicher Sprachen]]. Beispielsweise ist das Alphabet der [[Lateinisches Alphabet|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 [[Buchstabe]]n darstellt. Zum Beispiel ist <math>\Sigma = \{\mathit{do}, \mathit{re}, \mathit{mi}\}</math> ein Alphabet mit drei Elementen. Sie können in beliebiger Reihenfolge zusammenfügt werden, etwa zu <math>\mathit{do} {\color{red} \mathit{mi}} \mathit{do} {\color{red} \mathit{re}}</math>.

Hier ist dann die [[Arbitrarität]] der [[Symbol]]e besonders wichtig: Welche Zeichen für die Elemente des Alphabets verwendet werden, ist belanglos, solange sie voneinander unterscheidbar sind. Die Zeichenkette <math>\mathit{do} {\color{red} \mathit{mi}} \mathit{do} {\color{red} \mathit{re}}</math> 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 (Theoretische Informatik)|Wort]] bezeichnet. In vielen Computersprachen ist dafür die englische Bezeichnung ''{{lang|en|string}}'' im Gebrauch. Auch über dem lateinischen Alphabet ist also in der Informatik die Zeichenfolge <math>cdfg</math> ein Wort.

== Beispiele ==
* Mit Hilfe des Alphabets <math>\Sigma = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \rbrace</math> können alle [[Natürliche Zahl|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 [[Ziffer]]n und [[Zahlendarstellung]]en unterschieden. Eine [[Zahl]] ist dann ein Abstraktum, nämlich die Bedeutung ([[Semantik]], hier: Zahlenwert) einer [[Syntax|syntaktisch]] korrekten Zahlendarstellung.
* Das [[römische Zahlen]]system basiert in der Grundform auf dem Alphabet Σ = {I, V, X, L, C, D, M} (mit verschiedenen [[Römische Zahlschrift#Große Zahlen|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 <math>\Sigma_{D} = \{ dit, dah \}</math> bzw. <math>\{ .,- \}</math>, aus dem die Menge der Morsezeichen <math>L_D</math> auf Grundlage der einzelnen [[Buchstabenhäufigkeit]]en gebildet wird. Neben den Buchstaben und Zahlen ist unter anderem auch SOS (<math>...---...</math>) 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#Morse-Code|Präfixcode]]. Das Morsealphabet selbst besteht also insgesamt aus den Zeichen und der Pause zwischen den Zeichen: <math> \Sigma_{M} = L_D \cup \{ \text{PAUSE} \}</math>.

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 [[Termkalkül|Terme]] und [[Aussage (Logik)|Ausdrücke]] dieser Logik aufzubauen.

=== Definition eines Alphabet einer Prädikatenlogik erster Stufe ===
Das Alphabet einer ''[[Prädikatenlogik erster Stufe]]'' umfasst die folgenden Zeichen:<ref>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.</ref>

# <math>v_0, v_1, v_2, \ldots \ -</math>  [[Variable (Logik)|Variablenbezeichner]];
# <math>\neg, \wedge, \vee, \rightarrow, \leftrightarrow \ -</math>  [[Junktor]]en: Negation (nicht), Konjunktion (und), Disjunktion (oder), Implikation (wenn - dann), Äquivalenz (genau dann wenn);
# <math>\forall, \exists \ -</math>  universaler und existenzieller [[Quantor]];
# <math>\equiv \ -</math>  [[Gleichheitszeichen]];
# <math>),(,\boldsymbol{,} \ -</math>  technische Zeichen: Klammersymbole und Komma;
# des Weiteren
::a)  eine (eventuell leere) Menge von Konstantensymbolen;
::b)  für jedes ''n'' <math>\ge</math> 0 eine (eventuell leere) Menge von ''n''-stelligen Relationssymbolen;
::c)  für jedes ''n'' <math>\ge</math> 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 ''A<sub>S</sub>'' die Vereinigung von ''A'' und ''S''. Man nennt ''A<sub>S</sub>'' 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 <math>\in</math> (siehe [[Menge (Mathematik)]]).

== Einzelnachweise und Bemerkungen ==
<references />

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Mathematische Logik]]

Alphabet (Informatik) - Versionsgeschichte

imported>Hgzh: /* Abgrenzung zur natürlichen Sprache */ fix Darkmode