Fachkonzept: Endlicher Automat als Akzeptor

Grundidee endlicher Automat

Mit einem zustandsbasierten System kann man überprüfen, ob Symbolfolgen bestimmte vorgegebene Eigenschaften haben. So lässt sich mit dem in der Abbildung gezeigten System testen, ob eine Zeichenfolge aus Ziffern und Punkten eine Python-Gleitkommazahl ohne Exponenten darstellt.

Die Idee der Überprüfung besteht darin, eine Symbolfolge nur dann zu akzeptieren, wenn sie bei der Verarbeitung das System vom Anfangszustand in ganz bestimmte, vorher festgelegte Zustände - man nennt sie Endzustände - überführt.

Im dargestellten zustandsbasierten System werden z.B. die Symbolfolgen 21.1 und .21 akzeptiert. Die Symbolfolgen 2.1.1 und 21 werden dagegen nicht akzeptiert.

Zustandsbasierte Systeme, die auf diese Weise Symbolfolgen verarbeiten, werden endliche (erkennende) Automaten oder Akzeptoren g

Woraus ist ein endlicher Automat zusammengesetzt?

Zustände

Wesentlicher Bestandteil dieses Automaten ist die endliche Menge der Zustände:

$$Z = {q_0, q_1, q_2, q_3, q_4, q_5}$$

Eingabesymbole

Der endliche Automat verarbeitet Symbole. Diese Symbole lassen sich zu einer endlichen Menge von Eingabesymbolen zusammenfassen:

$$E = {0, 1, 2, .}$$

Überführungsfunktion

Die Verarbeitungslogik besteht darin, dass die Verarbeitung eines Symbols den Automaten von einem aktuellen Zustand in einen neuen Zustand überführt. Diese Verarbeitungslogik kann mit einem Graphen (wie oben) oder mit einer Automatentafel beschrieben werden.

	0	1	2	.
$q_0$	$q_1$	$q_1$	$q_1$	$q_4$
$q_1$	$q_1$	$q_1$	$q_1$	$q_2$
$q_2$	$q_3$	$q_3$	$q_3$	$q_5$
$q_3$	$q_3$	$q_3$	$q_3$	$q_5$
$q_4$	$q_3$	$q_3$	$q_3$	$q_5$
$q_5$	$q_5$	$q_5$	$q_5$	$q_5$

Formal lässt sich eine solche Automatentafel als Überführungsfunktion deuten, die jedem Paar aus aktuellem Zustand und Eingabesymbol einen Folgezustand zuordnet.

$$f: Z \times E \rightarrow Z mit f(q_0, 0) = q_1, f(q_0, 1) = q_1, ...$$

Startzustand

Jede Verabeitung einer Symbolfolge beginnt in einem ausgezeichneten Anfangszustand:

$$z0 = q0$$

Endzustände

Für die Erkennung der zu akzeptierenden Symbolfolgen wird schließlich eine Menge von Endzuständen benötigt:

$$Z_E = {q_2, q_3}$$

Definition_ Endlicher Automat

Ein endlicher (erkennender) Automat bzw. ein Akzeptor ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:

einer nichtleeren, endlichen Menge $Z$ von Zuständen
einer nichtleeren, endlichen Menge $E$ von Eingabesymbolen
einer Überführungsfunktion $f : Z \times E \rightarrow Z$, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet
einem ausgezeichneten Element $z_0 \in Z$, dem Anfangszustand
einer (in der Regel nicht-leeren) Menge $Z_E \subseteq Z$ von Endzuständen

Endlicher Automat als Spracherkenner

Die Menge $E$ der Eingabesymbole eines endlichen Automaten $A = (Z, E, f, z_0, Z_E)$ kann als Alphabet einer Sprache aufgefasst werden.

Zusammenhang Sprache $leftrightarrow> Automat

Ein endlicher Automat $A = (Z, E, f, z_0, Z_E)$ akzeptiert ein Wort $w$ über dem Alphabet $E$, wenn der Automat bei der Verarbeitung von $w$ mit der Überführungsfunktion $f$ vom Anfangszustand $z_0$ in einen Endzustand aus $Z_E$ überführt wird.

Die Menge aller Wörter über dem Alphabet $E$, die vom Automaten $A = (Z, E, f, z_0, Z_E)$ akzeptiert werden, nennt man Sprache des Automaten $A$. Man bezeichnet sie mit $L(A)$.

Ein endlicher Automat ist also eine Verarbeitungseinheit, die Symbole eines Eingabeworts verarbeitet und sich dabei stets in einem bestimmten Zustand befindet. Anhand des Zustands am Ende der Verarbeitung kann dann festgestellt werden, ob das zu verarbeitende Eingabewort akzeptiert wird oder nicht.

Die Abbildung veranschaulicht eine solche Verarbeitungseinheit. Die Symbole des zu verarbeitenden Eingabeworts sind in einzelne Zellen eines Eingabebandes geschrieben. Bei der Berarbeitung des Eingabeworts werden die einzelnen Symbole des Worts mit einem Lesekopf erfasst. Abhängig vom jeweils gelesenen Symbol wird die eigentliche Verarbeitungseinheit in einen passenden Zustand versetzt. Die Verarbeitung endet, wenn der Lesekopf alle Symbole des Wortes erfasst hat. Befindet sich die Verarbeitungseinheit dann in einem Endzustand, so wird das Wort akzeptiert.