Eingabealphabet

Eingabealphabet (oft auch Σ) bezeichnet in der formalen Sprach- und Automatentheorie eine endliche, nicht leere Menge von Symbolen, aus der Strings gebildet werden. Ein String ist eine endliche Folge von Symbolen aus Σ, und Σ* bezeichnet die Menge aller endlichen Strings über Σ. Das Eingabealphabet ist damit der Alphabet, über das eine Sprache definiert wird, die von einem Automatenmodell akzeptiert oder analysiert wird.

In endlichen Automaten wie deterministischen (DFA) oder nichtdeterministischen Automaten (NFA) dient Σ als Eingabealphabet. Die Übergangsfunktion delta verarbeitet ein Zustands- und Symbolpaar aus Q × Σ und führt zu einem neuen Zustand. Sprachen L werden als Teilmengen von Σ* betrachtet, also L ⊆ Σ*.

Beispiele: Σ = {0, 1} ist das Binäralphabet; Σ* enthält alle binären Wörter. Eine Beispiel-Sprache über Σ könnte die Menge aller Wörter mit gerader Länge sein. In praktischen Anwendungen bestimmt die konkrete Aufgabenstellung das Eingabealphabet oft durch die zu analysierenden Zeichen, beispielsweise bei einem Scanner, der Quelltextzeichen aus einem bestimmten Zeichensatz umfasst.

Im Gegensatz zum Ausgabealphabet Γ, das bei Transducern oder Mealy-/Moore-Automaten verwendet wird, ist Σ das Eingabealphabet. Viele Modelle arbeiten zusätzlich mit einem weiteren Alphabet für Ausgaben, das unabhängig vom Eingabealphabet bleibt. Bei Turingmaschinen bezeichnet man außerdem das Bandalphabet oft als Erweiterung des Eingabealphabets; das Eingabealphabet spezifiziert lediglich die Symbole, die als Eingabe gelesen werden.