Alphabet (Informatik)

Grundbegriff und Wörter

Ein Alphabet ist in Informatik und mathematischer Logik eine endliche Menge voneinander unterscheidbarer Symbole, auch Zeichen, Buchstaben oder Symbole genannt. Es wird meist mit Σ (Sigma), seltener mit V für Vokabular, bezeichnet. Als Zeicheninventar stellt es die Grundlage formaler Sprachen bereit.

Oft wird zusätzlich verlangt, dass ein Alphabet nicht leer ist. Ein Alphabet ist ein Zeichenvorrat oder Zeichensatz, aber unabhängig von einer Zeichenkodierung; mit „Zeichensatz“ kann nämlich auch eine Kodierung gemeint sein. Nach DIN 44300 ist ein Alphabet genauer eine total geordnete endliche Menge unterscheidbarer Symbole, also ein Zeichenvorrat zusammen mit einer Totalordnung (Σ, ≤).

Ein Wort ist eine endliche Folge von Symbolen eines Alphabets. Die Kleenesche Hülle Σ* ist die Menge aller Wörter, die sich aus Zeichen von Σ bilden lassen. Σω bezeichnet die abzählbar unendlichen Folgen von Zeichen aus Σ, wobei ω = ℵ0 ist. Σ∞ = Σ* ∪ Σω umfasst endliche Sequenzen und unendliche Folgen.

Für jedes Wort w aus Σ* gibt es genau eine Zahl n mit w ∈ Σn; sie heißt Länge von w. Wichtige Operationen auf Wörtern sind Konkatenation (Verkettung), Potenz (mehrfaches Hintereinandersetzen) und Spiegelung.

Abgrenzung und Beispiele

Das Informatik-Alphabet verallgemeinert die Alphabete natürlicher Sprachen. Seine Elemente müssen nicht einzelne sichtbare Buchstaben sein: Σ = {do, re, mi} ist beispielsweise ein Alphabet mit drei Elementen. Diese Symbole können beliebig zu Wörtern zusammengesetzt werden, etwa domidore. Entscheidend ist nur, dass die Elemente unterscheidbar sind; ihre konkrete Darstellung ist beliebig. Dieselbe Zeichenfolge kann daher etwa eine Tonfolge oder eine Programmsteuerung mit drei Befehlen bedeuten.

In der Informatik heißt jede beliebige Folge von Zeichen eines Alphabets Wort; in vielen Computersprachen wird dafür auch string verwendet. Deshalb ist cdfg über dem lateinischen Alphabet ein Wort.

• Über Σ = {0,1,2,3,4,5,6,7,8,9} lassen sich natürliche Zahlen im Dezimalsystem darstellen. Dabei sind Ziffern Zeichen, Zahlendarstellungen Wörter und die Zahl selbst ein Abstraktum: ihre Bedeutung beziehungsweise ihr Zahlenwert.

• Das römische Zahlensystem verwendet in der Grundform Σ = {I, V, X, L, C, D, M}. Damit eine Zeichenfolge als römische Zahlendarstellung gilt, müssen komplexe Regeln erfüllt sein, zum Beispiel IV statt IIII und größere Einheiten links von kleineren. Diese Regeln lassen sich durch eine formale Grammatik darstellen. 13 und XIII sind verschiedene Darstellungen derselben abstrakten Zahl.

• Beim Morsecode beschreibt ΣD = {dit, dah} beziehungsweise {., -} die Ebene der einzelnen Signale. Daraus wird die Menge der Morsezeichen LD gebildet; SOS (...---...) ist direkt ein Morsezeichen, weil zwischen seinen dit und dah keine Pause liegt. Für Nachrichten braucht man sonst kurze Pausen zwischen den Zeichen, da manche Zeichen auch Anfang anderer Zeichen sind. Das Morsealphabet ist daher ΣM = LD ∪ {PAUSE}. Solche Beispiele zeigen, dass komplexe Kommunikationssysteme durch gegebenenfalls hierarchische Paare aus Alphabeten und zugehörigen Sprachen beschrieben werden können.

Alphabet der Prädikatenlogik erster Stufe

Die zugrundeliegende Sprache ist der zentrale Bestandteil einer Logik. Ihr Alphabet legt fest, welche Zeichen zum Aufbau von Termen und Ausdrücken zulässig sind.

Das Alphabet einer Prädikatenlogik erster Stufe enthält Variablenbezeichner v0, v1, v2, …; die Junktoren ¬, ∧, ∨, → und ↔ für Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz; die Quantoren ∀ und ∃; das Gleichheitszeichen ≡ sowie Klammern und Komma. Hinzu kommen eine eventuell leere Menge von Konstantensymbolen, für jedes n ≥ 0 eine eventuell leere Menge n-stelliger Relationssymbole und für jedes n ≥ 0 eine eventuell leere Menge n-stelliger Funktionssymbole.

Sind A die zuerst genannten Zeichen und S die zusätzlichen Symbole, dann ist AS die Vereinigung von A und S. AS heißt Alphabet der Prädikatenlogik erster Stufe, S heißt seine Symbolmenge. Zur Angabe eines solchen Alphabets genügt die Angabe seiner Symbolmenge. Fehlt das Gleichheitszeichen, muss die Symbolmenge mindestens ein Relationssymbol enthalten; sonst können keine Formeln gebildet werden. Die Sprache der Mengenlehre hat als Symbolmenge nur das zweistellige Relationssymbol ∈.