Ein Alphabet ist eine endliche Menge von Symbolen.
Symbole sind wohlunterscheidbare Objekte wie z.B. Buchstaben oder Ziffern.

Eine formale Sprache ist eine Menge von Zeichenketten (oder Wörtern). Die Zeichenketten werden aus den Zeichen eines Alphabets gebildet.


Beispiel

Alphabet A = {a, b}
Sprache L = {a, ab, aa, abb, aba, aab}

Sprachen können wie im Beispiel durch die Aufzählung ihrer Wörter charakterisiert werden. Eine andere Möglichkeit der Beschreibung besteht durch die Angabe von Regeln, anhand derer die Wörter der Sprache gebildet werden können. Ein formales Schema für derartige Regeln ist die EBNF.


Literatur

Einführung in die Automatentheorie, formale Sprachen und Kompexitätstheorie; John E. Hopcroft, Jeffrey D. Ullman, Addison-Wesley.