Endlicher Automat

Es seien $Q$ und $X$ nichtleere endliche Mengen, wobei die Elemente von $Q$ Zustände und die Elemente von $X$ Zeichen genannt werden. Die Menge $X$ heißt in diesem Zusammenhang auch ein Alphabet. Weiterhin sei $S\; =\; X*$ das freie Monoid über $X$.

Eine rechtsseitige unitäre $S$-Menge $(Q$_S,.) wird dann auch in der Form $(Q,X,.)$ notiert und als deterministischer endlicher (Halbgruppen-)Automat bezeichnet.

Es reicht dann in der Tat aus, die Operation $.\; :\; Q\; x\; X$ Q zu kennen, denn $q$ = q gilt, da die $S$-Menge unitär ist, und für jedes Wort $x$₁x₂...x_n aus $X+$ ist ja $q(x$₁x₂...x_n) = ((...((qx₁)x₂)...)x_n). in der $S$-Menge eindeutig festgelegt.

Jedes Wort $w$ aus $X*$ definiert also eine Transformation $t$_w : Q Q und die Abbildung $$ : X^* T_Q mit $$(w) = t_w für alle $w$ aus $X*$ ist ein Homomorphismus von dem freien Monoid $X*$ in das Monoid aller Transformationen auf $Q$. Das Bild $$(X^*) wird dann auch das Transformationsmonoid des Automaten $(Q,X,.)$ genannt.

Man kann nun deterministische endliche Automaten $(Q,X,.)$ benutzen, um bestimmte formale Sprachen als Teilmengen von $X*$ zu beschreiben. Dazu zeichnet man einen Anfangszustand $q$₀ aus $Q$ und eine (eventuell auch leere) Teilmenge $Q$_f von $Q$ als Endzustände aus und definiert für den Automaten $A\; =\; (Q,X,.,q$₀,Q_f) dann

(1)

Man sagt, der Automat $A$ erkennt oder akzeptiert die Sprache $L(A)$, und nennt eine beliebige formale Sprache $L$ aus $X*$ erkennbar, wenn es einen deterministischen endlichen Automaten $A$ mit $L\; =\; L(A)$ gibt.

Eine alternative Definition der Erkennbarkeit formaler Sprachen erfolgt mit Hilfe erkennender Monoide.

Für jedes endliche Alphabet $X$ ist $X*$ abzählbar unendlich und daher die Potenzmenge von $X*$ überabzählbar. Es gibt also über einem festen Alphabet $X$ stets überabzählbar viele verschiedene formale Sprachen. Für jede feste endliche Menge $Q$ mit $|Q|\; =\; n$ gibt es auch nur endlich viele verschiedene deterministische endliche Automaten $(Q,X,.)$. Da es auf die Bezeichnung der Menge $Q$ nicht ankommt, gibt es im wesentlichen nur endlich viele verschiedene deterministische Automaten mit $n$ Zuständen. Daher gibt es nur abzählbar viele verschiedene deterministische endliche Automaten und folglich auch nur abzählbar viele verschiedene erkennbare Sprachen. Es gibt also (überabzählbar viele) nicht erkennbare Sprachen. Man kann sogar leicht konkrete derartige Sprachen angeben (siehe unten).

Wählt man für einen beliebigen deterministischen endlichen Automaten $(Q,X,.)$ den Startzustand $q$₀ aus $Q$ beliebig und die Endzustandsmenge $Q$_f = Q, dann erkennt $A=(Q,X,.,q$₀,Q_f) die Sprache $L(A)\; =\; X*$, wält man dagegen $Q$_f= { } als leere Menge, so erkennt der Automat $A$ die leere Sprache $L\; =\; \{\}$.

Erkennt allgemein der Automat $A\; =\; (Q,X,.,q$₀,Q_f) die Sprache $L\; =\; L(A)$ und definiert man den Automaten $A\text{'}\; =\; (Q,X,.,q$₀,Q'_f), indem man $Q\text{'}$_f = Q \ Q_f setzt, so gilt offensichtlich $L(A\text{'})\; =\; X*\backslash \; L(A)$.

Die Menge aller durch deterministische endliche Automaten erkennbaren Sprachen ist daher abgeschlossen gegenüber Komplementbildung und enthält die beiden Sprachen $\{ \}$ und $X*$.

Erkennt der Automat $A\; =\; (Q,X,.,q$₀,Q_f) die Sprache $L\; =\; L(A)$ und der Automat $A\text{'}\; =\; (Q\text{'},X,.,q\text{'}$₀,Q'_f) die Sprache $L\text{'}\; =\; L(A\text{'})$, so erkennt der Produktautomat $A\; x\; A\text{'}\; =\; (Q\; x\; Q\text{'},X,(q$₀,q'₀),Q_f x Q'_f) offensichtlich genau den Durchschnitt von $L$ und $L\text{'}$.

Die Menge aller durch deterministische endliche Automaten erkennbaren Sprachen ist daher abgeschlossen gegenüber Durchschnitten und (da sich Vereinigungen als Komplemente und Durchschnitte darstellen lassen) Vereinigungen, insgesamt also eine Boolesche Algebra. Da es Sprachen gibt, die nicht durch deterministische endliche Automaten erkennbar sind (siehe unten), ist dies eine echte Unteralgebra der Potenzmenge von $X*$.

Sei $x$₁...x_n ein beliebiges Wort aus $X*$ und $L\; =\; \{\; x$₁...x_n } die aus diesem Wort bestehende einelementige Sprache. Definiere den deterministischen endlichen Automaten $A\; =\; (Q,X,.,q$₀,{ q_n }) auf der Zustandsmenge $Q\; =\; \{\; q$₀,..., q_n+1 } durch $q$_i.x_i+1 = q_i+1 für $i=0,...,n-1$und $q.x\; =\; q$_n+1 für alle anderen Kombinationen von Zuständen und Zeichen. Offensichtlich gilt dann $q$₀x₁...x_n = q_n und $q$₀w \= q_n für alle anderen Worte $w$ aus $X*$. Also gilt $L(A)\; =\; L$ und jede einelementige Sprache ist damit erkennbar. Da die Menge der erkennbaren Sprachen aber abgeschlossen gegenüber endlichen Vereinigungen ist, gilt der folgende Satz.

Jede endliche Sprache ist erkennbar.

Sei $A\; =\; (Q,X,.,q$₀,Q_f) ein deterministischer endlicher Automat, der die Sprache $L\; =\; L(A)$ erkennt und $n\; =\; |\; Q\; |$. Entweder gilt für jedes Wort $w\; =\; x$₁... x_k aus $L$ dann , womit $L$ eine endliche Sprache ist, oder es gibt mindestens ein Wort $w\; =\; x$₁...x_k aus $L$ mit $n$ k. Betrachte im zweiten Fall die Folge der Zustände $q$₀, q₁ = q₀ x₁,..., q_k= q_k-1x_k, die $A$ bei der Erkennung von $w$ durchl&auuml;ft. Da dies mehr als $n$ Zustände sind, kommt mindestens ein Zustand aus $Q$ doppelt vor, etwa $q$_i = q_j für . Dann läßt sich $w\; =\; xyz$ zerlegen in Teilworte $x=x$₁...x_i-1, y = x_i...x_j-1, z=x_j...x_k, wobei mindestens $y$ nicht das leere Wort ist. Dann gilt aber für jedes Wort $w$_l = x.y^l.z aus $X*$ für $l=0,1,2,...$ ebenfalls $q$₀w_l = q_k und $q$_k liegt in $Q$_f. Daher liegen alle $w$_l bereits in $L$. Diese Sprache ist also unendlich und enthält mit $w$₀ = xz ein Wort einer Länge kleiner als $n$. Es gilt also insbesondere $L(A)\; =\; \{ \}$ genau dann, wenn $L(A)$ kein Wort einer Länge kleiner als $|Q|$ enthält, was man algorithmisch entscheiden kann.

Betrachtet man weiterhin für den Fall, daß $L=L(A)$ unendlich ist, die Menge $Laengen(L)$ aller Längen von Wörtern $w$ aus $L$, so zeigt die eben durchgeführte Überlegung, daß in dieser Menge natürlicher Zahlen keine Lücken größer als $k$ auftreten können, da die Längen der Wörter $w$_l diesen Abstand haben. Treten also in $Laengen(L)$ für eine unendliche Sprache $L$ beliebig große Lücken auf, so kann diese Sprache von keinem deterministischen endlichen Automaten erkannt werden.

Die Sprache $L\; =\; \{\; an2|\; n=0,1,2...\; \}$ über dem Alphabet $X\; =\; \{\; a\; \}$ ist durch keinen deterministischen endlichen Automaten erkennbar, denn die Lücken zwischen den Längen $n2$ und $(n+1)2=\; n2+\; 2n\; +\; 1$ zweier aufeinander folgender Wörter aus $L$ werden beliebig groß.

Offensichtlich kann man in dem gerade angegebenen Beispiel die Exponentenfolge $n2$ durch jede größere Potenz von $n$, aber auch durch exponentiell wachsende Folgen wie $2n$ oder auch durch die Folge der Primzahlen ersetzen, denn auch diese weist nach einem bekannten Resultat der Zahlentheorie beliebig große Lücken auf.