Endlicher Automat

Ein endlicher Automat (englisch: finite state machine oder finite automaton) ist ein Rechenmodell eines primitiven Computers, das aus mehreren Zuständen und mehreren Übergängen besteht und das ein übergebenes Wort annehmen oder ablehnen kann.

Beispiel

Wir beschreiben einen endlichen Automaten informell durch ein Zustandsdiagramm, das den endlichen Automaten beschreibt:

Der Automat besteht aus Zuständen, in der Abbildung gibt es drei runde Zustände q₀, q₁ und q₂. Zwischen diesen Zuständen gibt es Übergänge, das sind die Pfeile. Außerdem muss es einen Anfangszustand im Automaten geben, das ist der Zustand q₀. Der Anfangszustand wird oft durch einen Pfeil dargestellt, der von keinem Zustand kommt. Dann gibt es typischerweise einen Endzustand im Automaten, dieser wird durch eine Doppellinie dargestellt, im Bild ist es also der Zustand q₂.

Der auf diese Weise konstruierte Automat erhält einige Wörter. Wir geben also einige Wörter in den Automaten ein, der Automat versucht, diese Wörter zu akzeptieren. Wenn er sie annimmt, antwortet der Automat mit JA, wenn er sie nicht annimmt, antwortet er mit NEIN. Unser Automat versucht, Wörter zu akzeptieren, die aus den Buchstaben "a, b, c" bestehen, also können wir versuchen, das Wort "abbc" zu akzeptieren.

Wir beginnen im Ausgangszustand q₀ und die Eingabe ist das Wort "abbc". Als nächstes folgen wir den Pfeiltasten.

Wir gehen das Wort klassisch von links nach rechts durch, d.h. wir nehmen zuerst das Symbol "a". Der Pfeil für die Eingabe "a" geht zum Zustand q₁, also gehen wir dorthin und entfernen das Symbol "a" aus dem Wort. In der Eingabe haben wir das Wort "bbc":

Der Pfeil für die Eingabe "b" geht zurück zum Knoten q₁. Wieder entfernen wir den ersten Buchstaben und haben das Wort "bc" als Eingabe. Auch hier bleiben wir im Zustand q₁. Schließlich haben wir das Wort "c" als Eingabe. Vom Zustand q₁ führt uns der Pfeil für die Eingabe "c" in den Zustand q₂.

Wir haben bereits alle Buchstaben des Eingabewortes verbraucht und befinden uns im Zustand q₂, der der Endzustand ist. Dieser endliche Automat nimmt also das Wort "abbc" an.

Würden wir uns am Ende nicht im Empfangszustand befinden, würde der Automat das Wort nicht akzeptieren. Ebenso würde der Automat das Wort nicht akzeptieren, wenn wir uns in einem Zustand befänden, in dem wir nirgendwo hingehen könnten. Um zum Beispiel "ab" einzugeben, müssten wir uns im Zustand q₁ befinden und würden dort enden - der Automat akzeptiert dieses Wort nicht. Wenn wir das Wort "aabbc" ausprobieren würden, hätten wir wieder Pech, weil es für den Buchstaben "a" keinen Pfeil gibt, der aus dem Zustand q₁ führt.

Der endgültige Automat wird also verwendet, um eine Reihe von Wörtern zu erkennen. In der Praxis könnten wir den Automaten zum Beispiel verwenden, um festzustellen, ob ein gegebenes Eingabewort eine gültige E-Mail ist.

Definition eines endlichen Automaten

Um weiter und besser mit Automaten arbeiten zu können, müssen wir die bisherige intuitive Vorstellung davon, was ein endlicher Automat ist, formalisieren.

Wir werden sagen, dass ein endlicher (deterministischer) Automat ein Fünffach $\left<Q, \Sigma, \delta, q_0, F\right>$ ist, wobei

• Q eine endliche Menge von Zuständen ist,
• $\Sigma$ (großes Sigma) ein Alphabet ist (endliche Menge von Symbolen/Buchstaben),
• $\delta: Q \times \Sigma\longrightarrow Q$ die Übergangsfunktion ist,
• q₀ ∈ Q der Anfangszustand ist,
• F ⊆ Q die Menge der Endzustände (Empfangszustände) ist.

Kehren wir zum vorherigen Automaten zurück,

können wir sagen, dass es drei Zustände in der Menge der Zustände Q Q = {q₀, q₁, q₂} gibt. Das Alphabet $\Sigma$ enthält Buchstaben, aus denen wir Wörter zusammenstellen können, die der Automat dann akzeptiert oder ablehnt. In diesem Fall handelt es sich wahrscheinlich um das Alphabet $\Sigma=\left\{a, b, c\right\}$, aber es kann eine beliebige Obermenge sein. Der Anfangszustand von q₀ ist der Zustand von q₀, daran ändert sich nichts. Die Menge der Endzustände hat in diesem Automaten nur einen Zustand F = {q₂}.

Die Übergangsfunktion sind dann die drei Pfeile mit Buchstaben. Wenn Sie durch die Markierung $\delta: Q \times \Sigma\longrightarrow Q$ verwirrt sind, bedeutet das nur, dass δ eine Funktion (vielleicht besser eine Ansicht) ist, die zwei Parameter annimmt: den Zustand von Q und den Buchstaben von $\Sigma$. Wenn die Funktion aufgerufen wird, gibt sie einen neuen Zustand zurück. Wir könnten unsere Übergangsfunktion mit einer Tabelle wie folgt definieren:

$$ \begin{array}{cc|c} Q&\Sigma&\rightarrow Q\\\hline q_0&a&q_1\\ q_1&b&q_1\\ q_1&c&q_2\\ \end{array} $$

Wenn wir also δ(q₁, c) aufrufen, wenden wir die dritte Zeile an und die Funktion antwortet mit dem Zustand q₂ - genau wie im Diagramm. Wenn wir uns im Zustand q₁ befinden und die Eingabe der Buchstabe "c" ist, erhalten wir den Zustand q₂. Bevor wir formell definieren, was es für einen Automaten bedeutet, ein Wort zu akzeptieren, wollen wir unser intuitives Verständnis dieses Konzepts nutzen, um einige weitere Beispiele zu zeigen.

Andere Beispiele

1. Erstellen Sie einen Automaten, der über ein binäres Alphabet operiert, d.h. $\Sigma=\left\{0,1\right\}$, und nur Wörter akzeptiert, die auf eine Eins enden. Zum Beispiel akzeptiert er die Wörter 1, 01, 000001, 0101011.

   

   Unser Automat hat zwei Zustände - den Anfangszustand q₀ und den Endzustand q₁. Immer, wenn wir die Ziffer 1 als Eingabe haben, gehen wir in den Endzustand q₁ und bleiben dort. Umgekehrt, wenn die Eingabe eine Ziffer 0 ist, gehen wir in den Nicht-Endzustand q₀ und bleiben auch in diesem Zustand.

2. Konstruieren Sie einen Automaten über einem binären Alphabet, der nur Wörter akzeptiert, deren Anfangsbuchstabe sich vom Endbuchstaben unterscheidet.

   

   Der Automat teilt sich gleich im ersten Schritt in zwei "Unterautomaten". Wenn das Wort mit einer Null beginnt, geht der Automat in den linken Teil und bleibt dort, wenn es mit einer Eins beginnt, geht er in den rechten Teil. Dann ist es klassisch, wenn wir im linken Teil sind und eine 1 in der Eingabe ist, geht er in den Endzustand und bleibt dort. Wenn der Eingang 0 ist, gehen wir in den Zustand q₁, der nicht der Endzustand ist.

   Im Gegensatz zu den vorherigen Automaten hat dieser Automat mehrere Endzustände, nämlich F = {q₃, q₄}.

3. Konstruieren Sie einen Automaten über einem binären Alphabet, der nur Wörter akzeptiert, die nicht zwei aufeinanderfolgende Nullen enthalten.

   

   Dieser Automat ist aus zwei Gründen interessant: Der erste ist, dass er leere Wörter akzeptiert. Wir können versuchen, ein leeres Wort in den Automaten einzugeben, und der Automat wird es akzeptieren, wenn der Anfangszustand auch der Endzustand ist, was bei diesem Automaten der Fall ist. Da ein leeres Wort ein Wort ist, das nicht zwei Nullen hintereinander enthält, ist das die richtige Vorgehensweise. Interessant ist auch, dass dieser Automat alle Endzustände hat. Das einzige Mal, dass der Automat ein Wort nicht annimmt, ist also, wenn es keinen Übergang aus dem Zustand gibt. Dies geschieht im Zustand q₁, der keinen Übergang für 0 hat, denn dann würde das Wort zwei Nullen in einer Reihe enthalten.

4. Konstruieren Sie einen Automaten über das Alphabet {-,+,..,0,1,...,9}, der nur Wörter akzeptiert, die eine Zahl darstellen. Das heißt, entweder eine ganze Zahl wie 2, 548, 98263, oder eine Dezimalzahl wie 5584,48, 3,14, und zwar sowohl mit einer Version für eine negative Zahl mit Minuszeichen -2, -548, -3,14, als auch mit einem expliziten Pluszeichen, also +2, +548, +3,14. Gleichzeitig müssen wir in der Lage sein, die Zahl 0,123 einfach als .123 zu schreiben (ohne die führende Null), und zwar mit beiden Vorzeichen. Wir werden eine Notation einführen, bei der wir anstelle von zehn Übergängen für zehn Ziffern das Symbol N verwenden.

   

5. Konstruieren Sie einen Automaten über dem binären Alphabet, der nur Wörter der Form 0ⁿ1ⁿ akzeptiert, was bedeutet, dass die Wörter eine bestimmte Anzahl von Nullen am Anfang haben, gefolgt von einer gleichen Anzahl von Einsen. Beispiele für solche Wörter sind 0011, 00001111, 01.

   Wir können einen solchen Automaten nicht bauen, weil wir uns die Anzahl der Nullen nirgendwo "merken" können. Wir müssten mehrere "Unterautomaten" erstellen, wie im zweiten Beispiel, aber es müsste unendlich viele von diesen "Unterautomaten" geben, einen für jeden Wert von n.

Formalisierung der Berechnung des Automaten

Wir haben den endlichen Automaten selbst bereits formell definiert. Als nächstes müssen wir noch definieren, was ein solcher Automat eigentlich tut, d.h. wir definieren die Berechnung des Automaten.

Konfiguration des Automaten: Wir sagen, dass das Paar $\left<q, w\right> \in Q \times \Sigma^\ast$ die Konfiguration des Automaten ist, wobei q der aktuelle Zustand ist, in dem sich der Automat befindet, und w der ungelesene Teil des Wortes ist. $\Sigma^\ast$ bezeichnet die Schließung des Alphabets $\Sigma$, die Menge aller Wörter, die aus den Buchstaben des Alphabets $\Sigma$ zusammengesetzt werden können. Die Schließung schließt das leere Wort ein, das wir mit $\varepsilon$ bezeichnen.

Wenn wir einen Automaten $\left<Q, \Sigma, \delta, q_0, F\right>$ haben und versuchen, das Wort w zu akzeptieren, dann befindet sich der Automat in der Anfangskonfiguration <q₀, w>. Wenn wir zum Automaten zurückkehren

und versuchen, das Wort w = abbc zu akzeptieren, dann ist die Anfangskonfiguration <q₀, abbc>.

Wir definierenden Berechnungsschritt als eine Beziehung $\mapsto$ zwischen den Mengen $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, d.h. zwischen den Konfigurationen des Automaten. w = w₀w₁… w_n sei der ungelesene Teil des Wortes w. Dann sagen wir, dass die Paare <q₁, w₀w₁… w_n> und <q₂, w₁… w_n> in der Sitzung $\mapsto$ sind, geschrieben als

$$ \left<q_1, w_0w_1\dots w_n\right> \mapsto \left<q_2, w_1\dots w_n\right>, $$

nur dann, wenn δ(q₁, w₀) = q₂. Um zu unserem Beispiel zurückzukehren, die Anfangskonfiguration ist <q₀, abbc>. Aus dem Diagramm können wir ersehen, dass wir für die Eingabe "a" in den Zustand q₁ wechseln können. Wir können also schreiben

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right>, $$

weil δ(q₀, a) = q₁ gilt. Damit haben wir einen Schritt der Berechnung durchgeführt - wir haben uns angesehen, welchen Zustand wir für eine bestimmte Eingabe (= den ersten Buchstaben des ungelesenen Teils des Wortes) einnehmen sollten, uns dorthin bewegt und den ersten Buchstaben aus dem ungelesenen Teil des Wortes entfernt. Damit hatten wir eine neue Konfiguration.

Wir bezeichnen denreflexiven und transitiven Abschluss des Sitzungsschritts der Berechnung mit $\mapsto^\ast$. Wenn wir also $K_1 \mapsto^\ast K_2$ schreiben, wobei K₁, K₂ die Konfigurationen des Automaten sind, bedeutet dies, dass wir von der Konfiguration K₁ zur Konfiguration K₂ gelangen können, oder dass es eine endliche Folge solcher Konfigurationen gibt:

$$ K_1 \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_2 $$

Zum Beispiel in unserem Automaten, $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, denn wenn wir zwei Rechenschritte durchführen, bleiben wir bei dem Wort "bc" und bleiben im Zustand q₁. Das heißt, es gibt diese Folge von Konfigurationen:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> $$

Der Automat akzeptiert das Wort w dann und nur dann, wenn es eine q_f ∈ F gibt, die so beschaffen ist, dass $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ Das heißt, der Automat akzeptiert das Wort w dann und nur dann, wenn es eine solche Folge von Rechenschritten gibt, dass wir am Ende dieser Folge das ganze Wort gelesen haben und uns im Endzustand des Automaten befinden. Dass wir das ganze Wort gelesen haben, wird dadurch ausgedrückt, dass es in der Konfiguration anstelle des Wortes $\varepsilon$ steht, das ein leeres Wort ist. Unser Automat akzeptiert das Wort abbc, weil diese Folge von Konfigurationen existiert:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> \mapsto \left<q_1, c\right> \mapsto \left<q_2, \varepsilon\right> $$

und der Zustand q₂ ist der Endzustand, q₂ ∈ F.

Die vom Automaten akzeptierte Sprache ist die Menge aller vom Automaten akzeptierten Wörter. Wir bezeichnen die Sprache des Automaten A als L(A). Somit sind $L(A) \subseteq \Sigma^\ast$ und

$$ L(A) = \left\{w \in \Sigma^\ast,|,A \mbox{ akzeptiert das Wort } w\right\} $$

Eine reguläre Sprache ist eine Sprache, die von einem endlichen Automaten akzeptiert wird.

Zwei endliche Automaten sind äquivalent, wenn sie die gleiche Sprache akzeptieren. Das heißt, die Automaten A₁ und A₂ sind äquivalent, wenn L(A₁) = L(A₂) gilt.

Ressourcen

• M. Sipser: Einführung in die Rechentheorie
• Aho, Sethi, Ullman: Compiler: Prinzipien, Techniken und Werkzeuge