Syntaktisches Monoid


Es sei (S,*) eine Halbgruppe und L eine Teilmenge von S. Durch

(1)

x ~L y   <=>    für alle u,v aus S liegt das Produkt u * x * v genau dann in L, wenn das Produkt u * y * v in L liegt

für alle x,y aus S wir dann eine Kongruenzrelation auf (S,*) definiert.

Ist (S,*) sogar ein Monoid, so ist L Vereinigung von Kongruenzklassen.

Offensichtlich ist ~L nämlich symmetrisch und reflexiv. Gilt neben x ~L y auch noch y ~L z, so liegt für alle u,v aus S das Produkt u * x * v genau dann in L, wenn das Produkt u * z * v in L liegt. Also ist ~L auch transitiv und damit eine Äquivalenzrelation.

Sind nun x,y,z Elemente aus S mit x ~L y, so folgt für alle u,v aus S: Genau dann liegt (u*z) * x * v in L, wenn (u*z) * y * v in L liegt. Wegen (u*z) * x * v = u * (z*x) * v und (u*z) * y * v = u * (z*y) * v und (1) gilt also auch z*x ~L z*y. Links-rechts-dual folgt x*z ~L y*z. Also ist ~L eine Kongruenzrelation.

Für jedes x aus S bezeichne im folgenden [x] die Kongruenzklasse, in der x liegt.

Besitzt nun (S,*) ein Einselement e und ist x ein Element aus L, so folgt für jedes y aus [x] und u=v=e aus uxv=x in L auch y = uyv in L, d. h. die Klasse [x] ist vollständig in L enthalten. Damit ist L natürlich gleich der Vereinigung aller Klassen [x], wenn x ganz L durchläuft.


Ist jetzt X ein beliebiges Alphabet, also eine nichtleere endliche Menge, und L eine formale Sprache über X, also eine beliebige Teilmenge des freien Monoids X*, so bezeichnet man die Kongruenzrelation ~L auf X* als syntaktische Kongruenz von L und das Restklassenmonoid M(L) = X*/~L als syntaktisches Monoid von L.

Man sagt, ein Gruppoid (S,*) teilt ein Gruppoid (T,*), wenn es ein Untergruppoid (T',*) von (T,*) und einen surjektiven Homomorphismus : T' S gibt. Man schreibt dies auch als S < T.

Die Relation < zwischen Gruppoiden ist reflexiv, denn man kann T' = T = S und als identische Abbildung auf S wählen.

Die Relation < ist auch transitiv, denn aus U < S und S < T folgt die Existenz von Untergruppoiden T' von T und S' von S sowie surjektiven Homomorphismen : T' S und : S' U. Dann ist aber auch o : T' U surjektiv und es gilt daher U < T.

Gilt S < T und ist T endlich, so ist auch T' und damit S = (T') endlich.

Satz: Es seien L eine formale Sprache über dem Alphabet X und M,N Monoide.
a) Genau dann erkennt M die Sprache L, wenn M(L) < M gilt.
b) Gilt M < N und wird L von M erkannt, dann wird L auch von N erkannt.

Beweis: a) Wenn M die Sprache L erkennt, gibt es einen Homomorphismus : X* M und eine Teilmenge P von M mit L = -1(P). Sei N = (X*). Dann ist N Untermonoid von (M,*). Gilt (u) = (v) und liegt x*u*y in L für x,y aus X*, so folgt, daß (x*v*y) = (x*u*y) in (L) = P liegt. Also liegt x*v*y ebenfalls in -1(P) = L. Aus (u) = (v) folgt daher stets u ~L v. Also definiert ((u)) = [u] einen Homomorphismus von N in M(L), der offensichtlich surjektiv ist. Daher gilt M(L) < M.
Zum Nachweis der Umkehrung betrachte den kanonischen Homomorphismus : X* M(L) mit (w) = [w] für alle w aus X*. Dann ist P = (L) Teilmenge von M(L) mit L = -1(P), da L Vereinigung von Kongruenzklassen ist. Also wird L stets von M(L) erkannt.
Gelte jetzt M(L) < M. Dann existiert ein Monoid N, ein injektiver Homomorphismus : N M und ein surjektiver Homomorphismus : N M(L). Da X* freies Monoid ist, existiert ein Homomorphismus . X* N mit = o . Dann ist P = (-1((L))) Teilmenge von M und es gilt ( o )-1(P) = -1(-1(P)) = -1(-1((-1((L)))) = -1(-1((L))) = -1((L)) = L. Also erkennt M ebenfalls L.
b) Nach a) gilt M(L) < M. Mit M < N und der Transitivität folgt dann auch M(L) < N. Hieraus erhält man wiederum mit a) aber bereits die Behauptung.

Aus diesem Satz ergibt sich sofort eine weitere Charakterisierung der erkennbaren Sprachen.

Satz: Eine formale Sprache L ist genau dann erkennbar, wenn ihr syntaktisches Monoid M(L) endlich ist.

Mit Hilfe dieses Satzes kann man leicht für zahlreiche formale Sprachen nachweisen, daß sie nicht erkennbar sind. Wäre beispielsweise die Sprache L = { an bn | n=0,1,2,...} erkennbar, so wäre ihr syntaktisches Monoid M(L) endlich und es gäbe nur endlich viele verschiedene Kongruenzklassen bezüglich ~L. Sind aber m und k verschiedene natürliche Zahlen, so würde aus am ~L ak und aambm+1 in L auch ak+1bm+1 in L folgen, was nicht der Fall ist. Also sind die Klassen [am] und [ak] paarweise verschieden.