Endliche Automaten
Du willst wissen, was es mit dem Thema „endliche Automaten“ in der theoretischen Informatik auf sich hat? Hier erfährst du alles vom Prinzip, bis hin zu den Bestandteilen. Anschließend erklären wir dir noch die Funktionsweise an einem einfachen Beispiel.
Inhaltsübersicht
Endlicher Automat – Definition
Als Teil der Automatentheorie, wird ein endlicher Automat – auch Zustandsautomat oder Zustandsmaschine genannt – zur Modellierung eines bestimmten Verhaltens benutzt.
Bei endlichen Automaten handelt es sich im Grunde um eine Kombination aus Zuständen und Zustandsübergängen. Je nachdem, in welchem Zustand sich der endliche Automat befindet, erfolgen bei unterschiedlichen Eingaben jeweils andere Zustandsübergänge. Ein Zustandsübergang umfasst hierbei eine Änderung des Zustands und die Bedingungen, die für diese Änderung erfüllt sein müssen.
Außerdem gibt es für endliche Automaten noch vier Typen von Aktionen, die die Ausgabe generieren:
- Eingangsaktion: Beim Eintritt eines Zustands
- Ausgangsaktion: Beim Verlassen eines Zustands
- Eingabeaktion: Abhängig von der Eingabe und dem aktuellen Zustand
- Übergangsaktion: Abhängig von Zustandsübergang
Wichtig ist noch der Begriff des Alphabets. Das Eingabealphabet beispielsweise enthält alle Zeichen die in der Eingabe vorkommen können.
Zustandsautomat – Prinzip
Der Zustandsautomat befindet sich immer in genau einem Zustand. Stelle dir nun einen Geldautomaten vor: wenn der Automat nicht in Benutzung ist, wartet er auf das Einführen einer Karte, diese nennen wir in der Automatentheorie die „Eingabe“. Da dieser Zustand der „Grundzustand“ ist, mit welchem jede Nutzung des Automaten beginnen wird, nennt man diesen „Startzustand“. Er stellt den eindeutigen Startpunkt des Automaten dar. Eine Nutzung des Automaten endet entweder mit einer Geldausgabe oder mit einem Abbruch per Taste, was den Automaten jeweils in einen „Endzustand“ bringt.
Wichtig sind auch die Bedingungen, die mit Zustandsübergängen verknüpft sind. Im Beispiel des Geldautomaten wäre beispielsweise wichtig, dass der Nutzer seinen PIN-Code nur drei Mal eingeben darf.
Endliche Automaten akzeptieren eine Folge von Eingaben dann, wenn sie sich am Ende der Eingabefolge in einem Endzustand befinden. Ansonsten wird die Eingabe verworfen.
Präzisierung
Ein endlicher Automat kann mit wenigen Elementen in einem sogenannten 5-Tupel präzisiert werden, also einem Tupel, das aus fünf Elementen besteht. Grund dafür sind Verarbeitungseinheiten, die anhand des aktuellen Zustands Eingaben verwerten, dadurch den aktuellen Zustand ändern und manchmal sogar Ausgaben generieren.
Hierbei wird folgendes benötigt:
- die endliche Menge von Zuständen
- das Eingabealphabet
- eine Überführungsfunktion, die für jeden Zustand mit jeder Eingabe einen Folgezustand definiert
- die Menge der Startzustände
- die Menge der Endzustände
Zustandsübergangsdiagramm
Nun kennen wir die wichtigen Bestandteile eines endlichen Automaten. Doch wie werden diese sinnvoll dargestellt und angeordnet? Das Ganze passiert innerhalb eines Zustandsübergangsdiagramms. Die grafische Darstellung von endlichen Automaten baut sich wie folgt auf:
Der Startzustand wird mit einem Pfeil ohne vorhergehenden Zustand dargestellt. Manchmal wird der Pfeil alternativ auch von einem gefüllten Kreis aus gezeichnet.
Der Endzustand hingegen wird in einem Zustandsübergangsdiagramm als doppelt umkreister Zustand dargestellt. Alternativ hierzu wird manchmal ein Zustandsübergang vom Endzustand zu einem einfach umkreisten, gefüllten Kreis hinzugefügt.
Ein Zustandsübergang wird ganz simpel als Pfeil von Zustand 1 zu Zustand 2 veranschaulicht. Auf dem Pfeil steht hierbei die Eingabe beziehungsweise die Aktion, die zur Ausführung dieses Übergangs führt. Im Beispiel wäre dies „ausführen“.
Und ein Ereignis bezeichnet das Signal, welches ein Zustandsübergang bewirken kann.
Achtung: Führt kein Weg vom Startzustand zu einem Zustand z, dann gilt dieser als unerreichbar und kann entfernt werden. Oft kann dies gleich ganze Zustandsgruppen betreffen, wodurch dann ein ganzer Teil des Zustandsautomaten einfach entfernt und der endliche Automat insgesamt vereinfacht werden kann. Schau dir diesen Automaten an: Es gibt keine Möglichkeit den Zustand „beides“ zu erreichen, also kann er entfernt werden.
Eigentlich ist das Zustandsübergangsdiagramm ganz simpel, oder? Wenn du zusätzlich wissen möchtest, wie ein nichtdeterministischer Automat als Zustandsdiagramm aussieht, schau dir gerne unser Video dazu an.
Endliche Automaten – Aufgaben & Lösungen
Schauen wir uns das doch gleich an einem einfachen Beispiel an. Stellen wir uns einen Computer vor. Dieser kann entweder an oder aus sein. Der Übergang zwischen den Zuständen passiert durch das Hoch- beziehungsweise Herunterfahren des PCs.
Zustandsübergangsdiagramm – Aufgabe
Diesen Zustandsautomaten wollen wir nun als Zustandsübergangsdiagramm darstellen. Dazu beginnen wir mit den zwei Zuständen „an“ und „aus“. Nun fehlen nur noch die Pfeile, welche die Zustandsübergänge darstellen. Hierfür fügen wir einen Pfeil von „an“ zu „aus“ mit der Aufschrift „herunterfahren“ein. Dazu kommt ein weiterer Pfeil von „aus“ zu „an“ mit der Aufschrift „hochfahren“ hinzu. Fertig!
Übergangsmatrix
Zusätzlich zum Zustandsübergangsdiagramm kann eine Übergangsmatrix bzw. -tabelle erstellt werden. Aus dieser lässt sich der volle Informationsgehalt eines Zustandsautomaten ablesen.
In der Tabelle wird hierzu jeder Zustandsübergang, also jeder Pfeil des Zustandsübergangsdiagramms, mit aktuellem Zustand, der Eingabe, eventueller Ausgabe und dem Folgezustand notiert.
Für unser Beispiel sieht das dann folgendermaßen aus:
Schauen wir uns eine Zeile mal genauer an. Diese definiert, dass der Automat, wenn er sich in Zustand „an“ befindet und als Eingabe „herunterfahren“ folgt, als neuen Zustand „aus“ zugewiesen bekommt. Eigentlich nicht schwer, oder?
Und in unserem Video über deterministische endliche Automaten (Aufgaben & Lösungen inklusive) findest du weitere Beispiele.
So, nun kennst du die Basics von endlichen Automaten. Dass ein so kompliziertes und gewieftes System hinter einem Kasten steckt, der dir mittels deiner Kreditkarte ein paar Geldscheine auswirft, hättest du nicht vermutet, oder?