Freie Halbgruppen und Monoide


Es sei A eine beliebige nichtleere Menge, die in diesem Zusammenhang auch Alphabet genannt wird und deren Elemente entsprechend Buchstaben oder allgemeiner Zeichen heißen.

Weiterhin bezeichne FA die Menge aller (endlichen) Worte oder Strings, d. h. aller endlichen Sequenzen (a1,...,an) von Elementen ai aus A. Mit | (a1,...,an) | = n bezeichnet man die Länge dieses Wortes. Dabei ist auch das leere Wort als Sequenz der Länge 0 eingeschlossen. Für Worte (a1,...,an) und (b1,...,bm) definiert man als innere Verknüpfung die Konkatenation gemäß

(1)

(a1,...,an) * (b1,...,bm) =(a1,...,an,b1,...,bm).

Diese Verknüpfung ist offenbar assoziativ und das leere Wort ist neutrales Element. Also ist (FA,*) ein Monoid, das freie Monoid über A. Die Abbildung : A FA gemäß (a) = (a) für alle a aus A ist nach der Definition der Gleichheit von Sequenzen injektiv und man identifiziert daher die Buchstaben aus A mit den Wörtern der Länge 1 aus FA. Die Abbildung w | w | ist offensichtlich ein surjektiver Homomorphismus von (FA,*) auf das Monoid (N0,+) der natürlichen Zahlen. Genau dann ist FA kommutativ, wenn A aus einem Element besteht, da für zwei verschiedene Elemente a und b aus A die Paare (a,b) = (a) * (b) und (b,a) = (b) * (a) aus FA verschieden sind. Außerdem ist genau in diesem Fall der Längenhomomorphismus ein Isomorphismus, also jedes freie Monoid (F{a},*) über einem einelementigen Alphabet isomorph zu dem Monoid (N0,+)

Man schreibt ein Wort (a1,...,an) auch kurz als a1...an und läßt das Verknüpfungssymbol bei der Konkatenation weg. Will man das leere Worte explizit ansprechen, so verwendet man meistens das Symbol oder auch , das natürlich nicht schon in A vorkommen darf. Wegen | w | = 0   <=>   w = ist jedes freie Monoid ein Monoid mit echter Längenfunktion im Sinn der folgenden Definition.

Ein Monoid (S,*) mit dem Einselement 1 heißt ein Monoid mit echter Längenfunktion, wenn es einen Homomorphismus : (S,*) (N0,+) gibt, der (s) = 0   <=>   s = 1 für alle s aus S erfüllt.

Für Elemente s,t mit s*t = 1 eines derartigen Monoids (S,*) folgt hieraus aber schon (s) + (t) = (1) = 0 und daher s = t = 1, d. h. außer dem Einselement ist kein Element invertierbar.

Aus der Definition der Gleichheit zweier Sequenzen, nämlich (a1,...,an) = (b1,..., bm) genau dann, wenn n=m und ai = bi für alle i=1,...,n gilt, folgt die Kürzbarkeit jedes freien Monoids. Daher sind freie Monoide Beispiele für Halbgruppen mit genau einem idempotenten Element, dem leeren Wort. Sie sind aber keine Gruppen.

Eine große Bedeutung besitzen freie Monoide FA in der Theorie der formalen Sprachen oder der Automatentheorie, wo sie meistens mit A* bezeichnet werden. Eine formale Sprache L wird dann als beliebige Teilmenge von A* definiert. (Vergleiche hierzu auch Kapitel IV.5 in Hebisch/Weinert.)


Man kann in der obigen Konstruktion auch das leere Wort fortlassen und gelangt so zu dem Begriff der freien Halbgruppe über A. Diese wird meist mit A+ bezeichnet. Sie besitzt keine idempotenten Elemente und ist ebenfalls kürzbar.


Eine Halbgruppe (S,*) heißt gleichteilbar, wenn für alle s,t,u,v in S aus s*t = u*v folgt, daß ein x aus S1 existiert mit s = u * x und x * t = v, oder ein y aus S1 mit u = s * y und t = y * v.

Jede Gruppe und jede freie Halbgruppe sind gleichteilbar.

Im Fall einer Gruppe setze man x = u-1 * s oder y = s-1 * u. Im Fall einer freien Halbgruppe FA sei s*t = u*v = a1...an mit ai aus A. Dann gibt es Indizes k,l aus { 0,1,...,n } mit s = a1...ak, t = ak+1...an und u = a1...al, v = al+1...an. Im Fall l < k sei x = al+1...ak, sonst y = ak+1...al, was für k = l das leere Wort sein darf. Dann lassen sich die behaupteten Gleichungen nachrechnen.


Die algebraische Bedeutung freier Halbgruppen (und Monoide) wird durch die folgenden Überlegungen deutlich.

a) Ist : A S eine beliebige Abbildung von A in eine Halbgruppe (S,*), dann existiert ein eindeutig bestimmter Homomorphismus * : A+ S mit *(a) = (a) für alle a aus A.

Ist nämlich * ein solcher Homomorphismus, so folgt

(2)

*(a1...an) = *(a1)*...**(an) = (a1)*...*(an)

für alle a1...an aus A+, d. h. * ist durch eindeutig bestimmt. Definiert man andererseits * gemäß *(a1...an) = (a1)*...*(an), so ist es offensichtlich ein Homomorphismus.

b) Daher sind die oben konstruierten Monoide A+ freie Halbgruppen über A im Sinn der folgenden abstrakten Definition.

Eine beliebige Halbgruppe (F,*) heißt eine freie Halbgruppe über A, wenn es eine Abbildung : A F gibt und für jede Halbgruppe (S,*) und jede Abbildung : A S einen eindeutig bestimmten Homomorphismus *: F S, der * o = erfüllt.

c) Für jedes Alphabet A gibt es bis auf Isomorphie genau eine freie Halbgruppe über A.

Ist zunächst (F,*) eine freie Halbgruppe mit der Abbildung : A F und setzt man (S,*) = (F,*) sowie = , so ist der eindeutig bestimmte Homomorphismus * offensichtlich die identische Abbildung auf F. Ist nun (F',*) eine weitere freie Halbgruppe mit der Abbildung ' : A F und setzt man (S,*) = (F',*) sowie = ', so gibt es genau einen Homomorphismus *: F F' mit * o = '. Vertauscht man die Rollen von F und F', so erhält man einen eindeutig bestimmten Homomorphismus '*: F' F mit '* o ' = . Es folgen '* o * o = und * o '* o ' = '. Daher sind die eindeutig bestimmten Homomorphismen * o '* und '* o * die identischen Abbildungen auf F' bzw. F, d. h. sowohl * als auch '* sind Isomorphismen.

d) Eine Halbgruppe (S,*) ist genau dann eine freie Halbgruppe, wenn jedes Element von S sich eindeutig als Produkt von Elementen aus S \ S2 darstellen läßt.

Offensichtlich hat jede Halbgruppe S = A+ diese Eigenschaft, denn dann ist S \ S2 = A, da S2 aus genau den Worten mit einer Länge größer als 1 besteht. Sei umgekehrt (S,*) eine Halbgruppe mit dieser Eigenschaft und A = S \ S2 sowie : A T eine Abbildung in eine beliebige Halbgruppe. Für s in S sei s = a1...an die eindeutige Darstellung mit Elementen aus A. Definiere * : S T durch *(s) = (a1)...(an). Dann ist offensichtlich der eindeutig bestimmte Homomorphismus auf S, der fortsetzt. Also ist S eine freie Halbgruppe.

e) Sei : A+ S ein Halbgruppenhomomorphismus und :T S ein surjektiver Halbgruppenhomomorphismus. Dann gibt es einen Homomorphismus *: A+ T mit = o *.

Wähle dazu für jedes a aus A ein Element (a) aus der nichtleeren Menge -1((a)) willkürlich aus. Dies ist möglich, da surjektiv ist. Also ist : A T eine Abbildung, die sich nach a) zu einem Homomorphismus * : A+ T fortsetzen läßt. Für alle a1...an aus A+ gilt dann aber (a1...an) = (a1)... (an) = ((a1))... ((an)) = ((a1)... (an)) = (*(a1...an)).