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 ein übergebenes Wort akzeptieren oder ablehnen kann.

Beispiel

Informell beschreiben wir den endlichen Automaten mit einem Zustandsdiagramm, das den endlichen Automaten darstellt:

Der Automat besteht aus Zuständen, in der Abbildung sind es drei runde Zustände q₀, q₁ und q₂. Zwischen diesen Zuständen gibt es Übergänge, das sind die Pfeile. Im Automaten muss außerdem ein Startzustand vorhanden sein, das ist der Zustand q₀. Der Startzustand wird oft so dargestellt, dass auf ihn ein Pfeil zeigt, der von keinem Zustand ausgeht. Weiter gibt es im Automaten typischerweise einen Endzustand, den zeichnen wir mit einer doppelten Linie, in der Abbildung ist das der Zustand q₂.

Ein so aufgebauter Automat akzeptiert bestimmte Wörter. Wir geben also Wörter in den Automaten ein, und der Automat versucht, diese Wörter zu akzeptieren. Akzeptiert er sie, antwortet der Automat JA, akzeptiert er sie nicht, antwortet er NEIN. Unser Automat versucht, Wörter zu akzeptieren, die aus den Buchstaben „a, b, c“ bestehen, wir können also versuchen, das Wort „abbc“ zu akzeptieren.

Wir beginnen im Startzustand q₀ und auf der Eingabe steht das Wort „abbc“. Weiter richten wir uns nach den Pfeilen.

Das Wort gehen wir klassisch von links nach rechts durch, das heißt, als Erstes nehmen wir das Symbol „a“. Der Pfeil für die Eingabe „a“ führt in den Zustand q₁, wir gehen also dorthin und entfernen das Symbol „a“ aus dem Wort. Auf der Eingabe steht das Wort „bbc“:

Der Pfeil für die Eingabe „b“ führt zurück in den Knoten q₁. Wieder entfernen wir den ersten Buchstaben und auf der Eingabe steht das Wort „bc“. Wieder bleiben wir im Zustand q₁. Schließlich haben wir auf der Eingabe das Wort „c“. Aus dem Zustand q₁ schickt uns der Pfeil für die Eingabe „c“ in den Zustand q₂.

Wir haben schon alle Buchstaben des Eingabeworts aufgebraucht und sind im Zustand q₂, der ein Endzustand ist. Dieser endliche Automat akzeptiert also das Wort „abbc“.

Wären wir am Ende nicht in einem akzeptierenden Zustand, würde der Automat das Wort nicht akzeptieren. Genauso würde der Automat das Wort nicht akzeptieren, wenn wir in einem Zustand nirgendwohin weitergehen könnten. Für die Eingabe „ab“ würden wir zum Beispiel in den Zustand q₁ gelangen und dort enden – der Automat akzeptiert ein solches Wort nicht. Testen wir das Wort „aabbc“, haben wir wieder Pech, denn aus dem Zustand q₁ führt kein Pfeil für den Buchstaben „a“.

Der endliche Automat dient also dazu, eine Menge von Wörtern zu erkennen. In der Praxis könnten wir einen Automaten zum Beispiel verwenden, um festzustellen, ob das eingegebene Wort eine gültige E-Mail-Adresse ist.

Definition des endlichen Automaten

Die vorherige intuitive Vorstellung davon, was ein endlicher Automat ist, müssen wir formalisieren, damit wir mit Automaten weiter und besser arbeiten können.

Wir sagen, ein endlicher (deterministischer) Automat ist ein Fünftupel ⟨Q, Σ, δ, q₀, F⟩, wobei

• Q eine endliche Menge von Zuständen ist,
• Σ (großes Sigma) ein Alphabet (endliche Menge von Symbolen/Buchstaben) ist,
• δ: Q × Σ ⟶ Q die Übergangsfunktion ist,
• q₀ ∈ Q der Startzustand ist,
• F ⊆ Q die Menge der Endzustände (akzeptierenden Zustände) ist.

Kehren wir zum vorherigen Automaten zurück,

dann können wir sagen, dass in der Zustandsmenge Q drei Zustände liegen, Q = {q₀; q₁; q₂}. Das Alphabet Σ enthält die Buchstaben, aus denen wir Wörter zusammensetzen können, die der Automat dann akzeptiert oder ablehnt. Hier ist es wahrscheinlich das Alphabet Σ= {a; b; c}, es kann aber auch eine beliebige Obermenge sein. Der Startzustand q₀ ist der Zustand q₀, daran ändert sich nichts. Die Menge der Endzustände hat in diesem Automaten nur einen Zustand, F = {q₂}.

Unter der Übergangsfunktion verstehen wir dann die drei Pfeile mit den Buchstaben. Wenn dich die Schreibweise δ: Q × Σ ⟶ Q verwirrt: Sie bedeutet nur, dass δ eine Funktion (genauer vielleicht eine Abbildung) ist, die zwei Parameter nimmt: einen Zustand aus Q und einen Buchstaben aus Σ. Beim Aufruf gibt die Funktion einen neuen Zustand zurück. Unsere Übergangsfunktion könnten wir durch eine Tabelle so definieren:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Rufen wir also δ(q₁, c) auf, wenden wir die dritte Zeile an und die Funktion antwortet mit dem Zustand q₂ – genau wie das Diagramm. Sind wir im Zustand q₁ und auf der Eingabe steht der Buchstabe „c“, gelangen wir in den Zustand q₂. Bevor wir formal definieren, was es bedeutet, dass ein Automat ein Wort akzeptiert, nutzen wir das intuitive Verständnis dieses Begriffs und zeigen einige weitere Beispiele.

Weitere Beispiele

1. Konstruiere einen Automaten, der über dem binären Alphabet arbeitet, also Σ= {0; 1}, und nur Wörter akzeptiert, die mit einer Eins enden. Er akzeptiert z. B. die Wörter 1, 01, 000001, 0101011.

   

   Unser Automat hat zwei Zustände – den Startzustand q₀ und den Endzustand q₁. Immer wenn auf der Eingabe die Ziffer 1 steht, gehen wir in den Endzustand q₁ und bleiben darin. Steht dagegen auf der Eingabe die Ziffer 0, gehen wir in den Nicht-Endzustand q₀ und bleiben ebenfalls darin.

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

   

   Der Automat teilt sich gleich im ersten Schritt in zwei „Teilautomaten“. Beginnt das Wort mit einer Null, tritt der Automat in den linken Teil ein und bleibt dort, beginnt es mit einer Eins, wechselt er in den rechten Teil. Dann ist es klassisch: Sind wir im linken Teil und auf der Eingabe steht 1, wechseln wir in den Endzustand und bleiben dort. Steht auf der Eingabe 0, wechseln wir in den Zustand q₁, der kein Endzustand ist.

   Im Unterschied zu den vorherigen Automaten hat dieser Automat mehrere Endzustände, also F = {q₃; q₄}.

3. Konstruiere einen Automaten über dem binären Alphabet, der nur Wörter akzeptiert, die nicht zwei Nullen hintereinander enthalten.

   

   Dieser Automat ist aus zwei Gründen interessant: Erstens akzeptiert er das leere Wort. Wir können versuchen, das leere Wort in den Automaten einzugeben, und der Automat akzeptiert es, wenn der Startzustand zugleich ein Endzustand ist, was bei diesem Automaten der Fall ist. Da das leere Wort ein Wort ist, das nicht zwei Nullen hintereinander enthält, ist das richtig so. Die zweite Besonderheit ist, dass bei diesem Automaten alle Zustände Endzustände sind. Der einzige Fall, in dem der Automat ein Wort nicht akzeptieren würde, ist, wenn aus einem Zustand kein Übergang herausführt. Das passiert im Zustand q₁, der keinen Übergang für 0 hat, denn sonst würde das Wort zwei Nullen hintereinander enthalten.

4. Konstruiere einen Automaten über dem Alphabet {-,+,.,0,1,…,9}, der nur Wörter akzeptiert, die eine Zahl darstellen. Das heißt entweder eine ganze Zahl wie z. B. 2, 548, 98263, oder eine Dezimalzahl wie z. B. 5584.48, 3.14, und beides auch in der Variante für negative Zahlen mit Minuszeichen -2, -548, -3.14 und auch mit explizit angegebenem Plus, also +2, +548, +3.14. Gleichzeitig müssen wir die Zahl 0.123 auch nur als .123 (ohne die Null am Anfang) schreiben können, und zwar mit beiden Vorzeichen. Wir führen eine Hilfsbezeichnung ein: Statt zehn Übergänge für zehn Ziffern aufzuschreiben, verwenden wir das Symbol N.

   

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

   Einen solchen Automaten kann man nicht konstruieren, weil wir uns nirgends die Anzahl der Nullen „merken“ können. Wir müssten mehrere „Teilautomaten“ bilden, ähnlich wie im zweiten Beispiel, nur müssten es unendlich viele „Teilautomaten“ sein, für jeden Wert von n einer.

Formalisierung der Berechnung des Automaten

Wir haben den endlichen Automaten selbst schon formal definiert. Weiter müssen wir noch definieren, was ein solcher Automat eigentlich tut, also die Berechnung des Automaten definieren.

Konfiguration des Automaten: Wir sagen, dass ein Paar ⟨q, w⟩ ∈ Q × Σ^∗ eine Konfiguration des Automaten ist, wobei q der aktuelle Zustand ist, in dem sich der Automat befindet, und w der noch nicht gelesene Teil des Wortes. Σ^∗ bezeichnet die Kleene-Hülle des Alphabets Σ, die Menge aller Wörter, die sich aus den Buchstaben des Alphabets Σ zusammensetzen lassen. Teil der Hülle ist auch das leere Wort, das wir mit ε bezeichnen.

Haben wir einen Automaten ⟨Q, Σ, δ, q₀, F⟩ und versuchen, das Wort w zu akzeptieren, dann befindet sich der Automat in der Anfangskonfiguration ⟨q₀, w⟩. Kehren wir zum Automaten

zurück und wollen das Wort w = abbc akzeptieren, dann ist die Anfangskonfiguration ⟨q₀, abbc⟩.

Einen Rechenschritt definieren wir als Relation ↦ zwischen den Mengen (Q × Σ^∗) × (Q × Σ^∗), also zwischen Konfigurationen des Automaten. Es sei w = w₀w₁… w_n der noch nicht gelesene Teil des Wortes w. Dann sagen wir, dass die Paare ⟨q₁, w₀w₁… w_n⟩ und ⟨q₂, w₁… w_n⟩ in der Relation ↦ stehen, wir schreiben

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

genau dann, wenn δ(q₁, w₀) = q₂. Kehren wir zu unserem Beispiel zurück: Die Anfangskonfiguration ist ⟨q₀, abbc⟩. Aus dem Diagramm sehen wir, dass wir für die Eingabe „a“ in den Zustand q₁ übergehen können. Wir können also schreiben

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

weil δ(q₀, a) = q₁ gilt. Damit haben wir einen Rechenschritt ausgeführt – wir haben nachgesehen, in welchen Zustand wir für die gegebene Eingabe (= den ersten Buchstaben des noch nicht gelesenen Teils des Wortes) gehen sollen, sind dorthin gegangen und haben aus dem nicht gelesenen Teil des Wortes den ersten Buchstaben entfernt. So haben wir eine neue Konfiguration erhalten.

Die reflexive und transitive Hülle der Relation Rechenschritt bezeichnen wir mit ↦ ^∗. Schreiben wir also K₁ ↦ ^∗ K₂, wobei K₁, K₂ Konfigurationen des Automaten sind, bedeutet das, dass wir aus der Konfiguration K₁ über mehrere Rechenschritte in die Konfiguration K₂ gelangen können, also dass es eine endliche Folge von Konfigurationen gibt, sodass:

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

In unserem Automaten gilt zum Beispiel ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, denn wenn wir zwei Rechenschritte ausführen, bleibt uns das Wort „bc“ und wir bleiben im Zustand q₁. Es gibt also diese Folge von Konfigurationen:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Der Automat akzeptiert das Wort w genau dann, wenn es ein q_f ∈ F gibt, sodass $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Das bedeutet, dass der Automat das Wort w genau dann akzeptiert, wenn es eine Folge von Rechenschritten gibt, sodass wir am Ende dieser Folge das ganze Wort gelesen haben und uns in einem Endzustand des Automaten befinden. Dass wir das ganze Wort gelesen haben, wird dadurch ausgedrückt, dass in der Konfiguration an der Stelle des Wortes ε steht, das leere Wort. Unser Automat akzeptiert das Wort abbc, weil es diese Folge von Konfigurationen gibt:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

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

Die vom Automaten akzeptierte Sprache ist die Menge aller Wörter, die der Automat akzeptiert. Die Sprache des Automaten A bezeichnen wir mit L(A). Es gilt also L(A) ⊆ Σ^∗ und

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid A\text{ akzeptiert das Wort }w\}$$

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

Zwei endliche Automaten sind äquivalent, wenn sie dieselbe Sprache akzeptieren. Die Automaten A₁ und A₂ sind also äquivalent, wenn L(A₁) = L(A₂) gilt.

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools