Definition: Eine endliche nichtleere Menge $\sum$ heisst Alphabet. Die Elemente eines Alphabets werden Buchstaben (Zeichen, Symbole) genannt.
Einige Beispiele:
Definition: Ein Wort über ein Alphabet $\sum$ ist eine endliche (eventuell leere) Folge von Buchstaben aus $\sum$. Das leere Wort $\lambda$ ist die leere Buchstabenfolge. $\Sigma^$ ist die Menge aller Wörter über $\Sigma$, $\Sigma^+$ ist die Menge aller Wörter über $\Sigma^$ ohne das leere Wort, also $\Sigma^+ = \Sigma^* - \{\lambda \}$.
Definition: Die Verkettung für ein Alphabet $\sum$ ist eine Abbildung $\text{Kon}: \sum^* \times \sum^* \to \sum^*$, so dass $\text{Kon}(x,y) = x \cdot y = xy$ ist.
Definition: Eine Sprache $L$ über ein Alphabet $\sum$ ist eine Teilemenge von $\sum^$. Das Komplement $L^C$ der Sprache $L$ bezüglich $\sum$ ist die Sprache $\sum^-L$.