Die Menge AA besteht aus den geordneten Paaren
<a1,a2> mit a1, a2
A.
Ebenso besteht A
A
A aus den Tripeln von Elementen aus A,
und ebenso für beliebig viele Faktoren A;
wir sprechen hier von Sequenzen über A,
und schreiben sie oft mit spitzen Klammern.
Wir können Sequenzen miteinander verknüpfen oder verketten, indem wir sie aneinanderhängen:
<a1,a2><a3,a4,a5> = <a1,a2,a3,a4,a5>diese Operation ist assoziativ .
Ist A ein Alphabet, also ein endlicher Zeichenvorrat,
so lassen wir bei den Sequenzen meist die spitzen Klammern und Kommas weg
und sprechen von Wörtern über dem Alphabet A.
Die Menge A selbst entspricht dann den Wörtern der Länge 1,
und oft nehmen wir ein leeres Wort ,
also die Sequenz <> der Länge 0, mit hinzu;
es ändert bei der Verkettung nichts
(es ist ein neutrales Element).
Die Menge aller endlichen Wörter über einem Alphabet A:
A* = {heißt in der Algebra freies Monoid über A; weshalb, tut hier nichts zur Sache.}
A
(A
A)
(A
A
A)
...
Jede Teilmenge L von A* nennen wir eine Formale Sprache (über A); fast alle davon sind unendlich , und wir können nur mit solchen praktisch umgehen, von denen es eine endliche Beschreibung gibt!
A* ist abzählbar, und damit auch alle Formalen Sprachen über A (soweit sie nicht ohnehin endlich sind); aber die Menge aller Formalen Sprachen über A ist überabzählbar. Andererseits gibt es nur abzählbar viele endliche Beschreibungen. Unsere Möglichkeiten erscheinen also recht stark eingeschränkt; aber für die Praxis genügen sie bei weitem.
Es ist oft bequem, auch eine assoziative Verkettung für Formale Sprachen einzuführen:
MN = { mn | mAuch hier gibt es ein neutrales Element oder Einselement, nämlich {M
n
N }
M{} = {
}M = M,
MØ = ØM = Ø