Erkennbare Sprachen

Es sei $X$ eine nichtleere endliche Menge, deren Elemente Zeichen genannt werden. Die Menge $X$ heißt in diesem Zusammenhang auch ein Alphabet. Weiterhin sei $X*$ das freie Monoid über $X$. Jede Teilmenge $L$ von $X*$ heißt eine formale Sprache über $X$.

Eine solche Sprache $L$ heißt erkennbar durch das Monoid $(M,*)$, wenn es einen Homomorphismus $$ : X^* M und eine Teilmenge $P$ von $M$ gibt, so daß $L\; =$^-1(P) gilt. Man nennt die Sprache $L$ ohne jeden weiteren Zusatz erkennbar, wenn sie durch ein endliches Monoid erkennbar ist.

Der Begriff der "Erkennbarkeit durch ein Monoid" ist zu allgemein, um mit ihm sinnvoll formale Sprachen charakterisieren zu können. Man kann nämlich für jede beliebige formale Sprache $L$ immer $M\; =\; X*,\; P\; =\; L$ und $$ als identische Abbildung wählen, um $L$ durch ein Monoid zu erkennen. Entscheidend ist also die Forderung der Endlichkeit von $M$.

Ist $M\; =\; \{\; 1\; \}$ die einelementige Gruppe, also ein Monoid, dann ist $$ : X^* M mit $$(w) = 1 für alle $w$ aus $X*$ ein Homomorphismus. Für $P\; =\; M$ zeigt $X*=$^-1(P), daß $L\; =\; X*$ für jedes Alphabet $X$ eine erkennbare Sprache ist.

Ersetzt man in der Definition der Erkennbarkeit durch ein Monoid die Menge $P$ durch ihr Komplement $M\; \backslash \; P$, so sieht man, daß mit einer formalen Sprache $L$ stets auch ihr Komplement $X*\backslash \; L$ erkennbar ist, denn aus $L\; =$^-1(P) folgt sofort $X*\backslash \; L\; =$^-1(M \ P).

Es seien $X$ und $Y$ Alphabete und $$ : X^* Y^* ein Homomorphismus. Wird dann die Sprache $L$ über $Y$ von einem Monoid $M$ erkannt, dann auch die Sprache $$^-1(L) über $X$.

Gilt nämlich $L\; =$^-1(P) für die Teilmenge $P$ von $M$ und den Homomorphismus $$ : Y^* M, so gilt $$^-1(L) = ^-1(^-1 (P)) = ( o )^-1(P) für den Homomorphismus $$ o .

Satz: Eine formale Sprache $L$ über einem Alphabet $X$ ist genau dann erkennbar, wenn es einen deterministischen endlichen Automaten $A=(Q,X,.,q$₀,Q_f) mit $L\; =\; L(A)$ gibt.

Beweis: Sei $(M,*)$ ein endliches Monoid, $P$ eine Teilmenge von $M$ und $$ : X^* M ein Homomorphismus mit $L\; =$^-1(P). Definiere den deterministischen endlichen Automaten $A\; =\; (Q,X,.,q$₀,Q_f) durch $Q\; =\; M$ (endlich!), $q$₀ = 1 ($(M,*)$ ist ein Monoid), $Q$_f = P (ist Teilmenge von $M\; =\; Q$) und $m.x\; =\; m*$(x) aus $M$ (ist im Monoid $(M,*)$ eindeutig definiert). Dann liegt ein Wort $w$ aus $X*$ in $L(A)$ genau dann, wenn $1.w$ in $P$ liegt, was aber wegen $1.w=1*$(w) = (w) gleichwertig dazu ist, daß $w$ in $$^-1(P) = L liegt. Also gilt $L(A)\; =\; L$.
Ist umgekehrt $A=(Q,X,.,q$₀,Q_f) ein deterministischer endlicher Automat, der die Sprache $L\; =\; L(A)$ erkennt, so ist $$ : X^* M(A) mit $$(w) = t_w ein Homomorphismus von $X*$ in das endliche Transformationsmonoid des Automaten. Sei $P\; =$(L). Offensichtlich ist $L$ in $$^-1((L))=^-1(P) enthalten. Sei also umgekehrt $v$ aus $$^-1(P). Also liegt $$(v) in $P\; =$(L), d. h. es gibt ein $w$ aus $L$ mit $$(v) = (w). Hieraus folgt $t$_v = t_w im Transformationsmonoid $M(A)$. Insbesondere gilt dann aber $q$₀.v = q₀.w und dieser Zustand ist ein Endzustand, da $w$ in $L\; =\; L(A)$ liegt. Daher liegt auch $v$ in $L(A)\; =\; L$. Also wird $L$ von dem (endlichen!) Transformationsmonoid $M(A)$ erkannt, ist also erkennbar.

Man kann also die Erkennbarkeit einer formalen Sprache sowohl mit Hilfe deterministischer endlicher Automaten als auch mittels endlicher Monoide definieren. Dabei reicht sogar das syntaktische Monoid der Sprache aus.