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 (QS,.) 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 x1x2...xn aus X+ ist ja q(x1x2...xn) = ((...((qx1)x2)...)xn). in der S-Menge eindeutig festgelegt.

Jedes Wort w aus X* definiert also eine Transformation tw : Q Q und die Abbildung : X* TQ mit (w) = tw 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 q0 aus Q und eine (eventuell auch leere) Teilmenge Qf von Q als Endzustände aus und definiert für den Automaten A = (Q,X,.,q0,Qf) dann

(1)

L(A) = { x1x2...xn aus X* | q0 (x1x2...xn) liegt in Qf}.

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 q0 aus Q beliebig und die Endzustandsmenge Qf = Q, dann erkennt A=(Q,X,.,q0,Qf) die Sprache L(A) = X*, wält man dagegen Qf= { } als leere Menge, so erkennt der Automat A die leere Sprache L = {}.

Erkennt allgemein der Automat A = (Q,X,.,q0,Qf) die Sprache L = L(A) und definiert man den Automaten A' = (Q,X,.,q0,Q'f), indem man Q'f = Q \ Qf setzt, so gilt offensichtlich L(A') = X* \ 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,.,q0,Qf) die Sprache L = L(A) und der Automat A' = (Q',X,.,q'0,Q'f) die Sprache L' = L(A'), so erkennt der Produktautomat A x A' = (Q x Q',X,(q0,q'0),Qf x Q'f) offensichtlich genau den Durchschnitt von L und L'.

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 x1...xn ein beliebiges Wort aus X* und L = { x1...xn } die aus diesem Wort bestehende einelementige Sprache. Definiere den deterministischen endlichen Automaten A = (Q,X,.,q0,{ qn }) auf der Zustandsmenge Q = { q0,..., qn+1 } durch qi.xi+1 = qi+1 für i=0,...,n-1und q.x = qn+1 für alle anderen Kombinationen von Zuständen und Zeichen. Offensichtlich gilt dann q0x1...xn = qn und q0w \= qn 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,.,q0,Qf) ein deterministischer endlicher Automat, der die Sprache L = L(A) erkennt und n = | Q |. Entweder gilt für jedes Wort w = x1... xk aus L dann k < n, womit L eine endliche Sprache ist, oder es gibt mindestens ein Wort w = x1...xk aus L mit n k. Betrachte im zweiten Fall die Folge der Zustände q0, q1 = q0 x1,..., qk= qk-1xk, 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 qi = qj für i < j. Dann läßt sich w = xyz zerlegen in Teilworte x=x1...xi-1, y = xi...xj-1, z=xj...xk, wobei mindestens y nicht das leere Wort ist. Dann gilt aber für jedes Wort wl = x.yl.z aus X* für l=0,1,2,... ebenfalls q0wl = qk und qk liegt in Qf. Daher liegen alle wl bereits in L. Diese Sprache ist also unendlich und enthält mit w0 = 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 wl 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.