Syntaktisches Monoid

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

(1)

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\text{'},*)$ von $(T,*)$ und einen surjektiven Homomorphismus $$ : T' S gibt. Man schreibt dies auch als .

Die Relation zwischen Gruppoiden ist reflexiv, denn man kann $T\text{'}\; =\; T\; =\; S$ und $$ als identische Abbildung auf $S$ wählen.

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

Gilt und ist $T$ endlich, so ist auch $T\text{'}$ 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 gilt.
b) Gilt 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 .
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 . 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 . Mit und der Transitivität folgt dann auch . 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\; =\; \{\; anbn|\; 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 a^k 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.