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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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?
Endliche Automaten — häufigste Fragen
(ausklappen)
Endliche Automaten — häufigste Fragen
(ausklappen)-
Was ist ein Automat in der Informatik?Ein Automat in der Informatik ist ein Modell, das ein Verhalten als endliche Menge von Zuständen und Zustandsübergängen beschreibt. Welche Übergänge passieren, hängt von der aktuellen Eingabe und dem aktuellen Zustand ab. Oft gibt es zusätzlich einen Startzustand und definierte Endzustände.
-
Was ist ein endlicher erkennender Automat?Ein endlicher erkennender Automat ist ein endlicher Automat, der Eingabefolgen darauf prüft, ob sie zu einer bestimmten Sprache (Menge von Zeichenfolgen) gehören. Er liest die Eingabe Schritt für Schritt und wechselt dabei Zustände. Akzeptiert wird genau dann, wenn der Automat nach der letzten Eingabe in einem Endzustand steht.
-
Was ist ein nichtdeterministischer endlicher Automat?Ein nichtdeterministischer endlicher Automat ist ein endlicher Automat, bei dem auf dieselbe Eingabe aus einem Zustand mehrere verschiedene Folgezustände möglich sein können. Im Zustandsübergangsdiagramm sieht man das als mehrere Pfeile mit gleicher Beschriftung vom selben Zustand aus. Akzeptiert wird eine Eingabe, wenn mindestens ein möglicher Ablauf in einem Endzustand endet.
-
Was ist der Unterschied zwischen einer Turingmaschine und einem endlichen Automaten?Der Unterschied zwischen einer Turingmaschine und einem endlichen Automaten ist vor allem die verfügbare „Speicherkapazität“ und damit die Rechenmacht. Ein endlicher Automat hat nur endlich viele Zustände und kein zusätzliches, unbegrenztes Gedächtnis. Eine Turingmaschine hat ein theoretisch unendlich langes Band, auf das sie lesen und schreiben kann.
Automatentheorie verstehen
Endliche Automaten gehören zur Automatentheorie und sind ein wichtiges Modell in der Informatik. Wer sich mit Automatentheorie beschäftigt, ordnet Zustände, Eingaben und Regeln zu klaren Abläufen. So wird verständlich, wie ein System auf Eingaben reagiert und von einem Zustand in den nächsten wechselt. Weitere Videos dazu findest du in unserem Informatikbereich.
