Inhaltsverzeichnis
Endliche Automaten
Ein deterministischer endlicher Automat (kurz: DEA) besteht aus
- einem endlichen Eingabealphabet $A$,
- einer endlichen Menge $Z$ von Zuständen,
- einer nichtleeren Teilmenge $E$ von Endzuständen und
- einem Startzustand $Z_0$ sowie
- einer Menge von Zustandsübergängen
(genauer: einer Funktion $\delta: Z\times A \rightarrow Z$, die jedem Tupel aus Zustand und Eingabezeichen einen Folgezustand zuordnet) .
Um herauszufinden, ob ein Wort aus $A^*$ vom Automaten akzeptiert wird, beginnt man im Startzustand des Automaten und geht - Buchstabe für Buchstabe - die entsprechend gekennzeichneten Übergänge entlang. Hat man das komplette Wort abgearbeitet und befindet sich der Automat in einem der Endzustände (gekennzeichnet durch Doppelkreise), so akzeptiert der Automat das Wort. Befindet sich der Automat am Ende nicht in einem Endzustand, so akzeptiert er das Wort nicht.
Die Menge aller vom Automaten akzeptierten Wörter ist eine Sprache über dem Alphabet A.
Weitere Definitionen:
- Der deterministische endliche Automat heißt deterministisch, weil es in jedem Zustand für jedes Zeichen des Eingabealphabets höchstens einen Zustandsübergang gibt. Ansonsten wäre $\delta$ auch keine Funktion.
- Ein endlicher Automat wird manchmal auch erkennender Automat genannt.
- Die Darstellung eines DEA heißt vollständig, wenn es in jedem Zustand für jedes Zeichen des Eingabealphabets einen Zustandsübergang gibt.
Bemerkung: Die Definitionen von "erkennender Automat" und "vollständig" finden sich im Lehrbuch "Informatik 7", nicht aber im bayerischen Lehrplan.
Im Gegensatz zur Beschreibung einer Sprache durch eine Grammatik liefert die Beschreibung durch einen endlichen deterministischen Automaten ein praktisches, einfach zu implementierendes Werkzeug, das erkennen kann, ob ein Wort zu einer Sprache gehört oder nicht.
Beispiel A
Der rechts gezeichnete Automat unten mit dem Eingabealphabet A = { "a", "b" } erkennt alle Wörter über A, die nichtleer sind und eine gerade Anzahl von a's haben.
Bemerkung zur Notation:: Da die Menge der Zustände (beschriftete Kreise), der Startzustand (mit Pfeil "Start" gekennzeichnet) und die Endzustände (Doppelkreise) aus dem Diagramm eindeutig hervorgehen, müssen sie nicht extra zusätzlich zum Diagramm angegeben werden.
Aufgabe 1
Erstellen Sie einen deterministischen endlichen Automaten mit dem Alphabet A = {0, 1}, der Binärzahlen verarbeitet und genau die geraden Binärzahlen akzeptiert.
Aufgabe 2
Ein elektronisches Schloss besitzt eine Tastatur mit den Ziffern 0, 1, …, .9. Im Inneren des Schlosses befindet sich ein Microcontroller, auf dem der im Diagramm dargestellte DEA implementiert ist. Beschreiben Sie, welche Ziffernfolgen er akzeptiert!
Aufgabe 3
Konstruieren Sie einen DEA mit dem Alphabet A = {0, 1}, der genau die Binärzahlen akzeptiert, die größer oder gleich der Dezimalzahl 12 sind.
Aufgabe 4:
Bearbeiten Sie Aufgabe VI 1. a) - d) des Informatikabiturs 2016.
Aufgabe 5:
Sowohl Grammatiken als auch deterministische endliche Automaten eignen sich dazu, Sprachen zu definieren. Beschreiben Sie den grundsätzlichen Unterschied in der Herangehensweise!
Nichtdeterministische endliche Automaten
Nichtdeterministische endliche Automaten sind solche, bei denen es mindestens einen Zustand gibt, für den mindestens ein Zeichen des Alphabets existiert, das einen Übergang zu mindestens zwei verschiedenen Folgezuständen bewirken kann.
Hier ein Beispiel für einen nichtdeterministischen endlichen Automaten mit dem Alphabet A = {a, b, …, z, A, B, …, Z}, der genau die Wörter Maus und Mond erkennt:
Die Funktion $\delta$, die bei DEAs die Zustandsübergänge vorgibt, ist bei nichtdeterministischen endlichen Automaten natürlich keine Funktion, sondern eine Relation.
Nichtdeterministische Automaten sind in praktischer Hinsicht schlecht brauchbar, denn sie müssen vorausschauend "ahnen", welcher von mehreren möglichen Übergängen erfolgen soll. Ist das Eingabewort für den oben angegebenen Automaten etwa "Maus", so kommt der Automat nur dann in den Endzustand Z4, wenn bei der Verarbeitung des "M" der Übergang nach Z1 gewählt wird.
Man kann beweisen, dass es zu jedem nichtdeterministischen endlichen Automat einen DEA gibt, der dieselbe Sprache akzeptiert. Dieser Beweis ist konstruktiv, d.h. er beschreibt das Vorgehen, mit dem der DEA aus dem nichtdeterministischen endlichen Automaten konstruiert werden kann. Für die Interessierten ist bspw. hier das Vorgehen beschrieben. Hier noch ein Video dazu.
Wie ein DEA aussehen kann, der die Sprache unseres Beispiels akzeptiert, lässt sich auch leicht durch Überlegen herausfinden:
Einen Zustand wie Z9, in den der Automat kommt, wenn das Erreichen eines Endzustandes nicht mehr möglich ist, nennt man Fehlerzustand (auch: Fangzustand).
Aufgabe 6:
Bearbeiten Sie im Buch "Informatik 7, gA" Aufgabe 1 auf Seite 29.
Aufgabe 7:
Bearbeiten Sie im Buch "Informatik 7, gA" Aufgabe 2 auf Seite 30.
Aufgabe 8:
Lesen Sie im Buch "Informatik 7, gA" den Text "Syntax vs. Semantik" auf Seite 28.
Aufgabe 9:
Bearbeiten Sie im Buch "Informatik 7, gA" Aufgabe 9 auf Seite 31.
Aufgabe 10:
Die Sprache L über dem Alphabet A = {x, y} bestehe aus allen Wörtern, die das Teilwort "xyxy" nicht enthalten.
- a) Zeichnen Sie einen DEA, der genau die Wörter aus L erkennt.
- b) Implementieren Sie Ihren DEA in Java.
Aufgabe 11:
Die Sprache L über dem Alphabet A = {x, y, -} bestehe aus dem leeren Wort sowie aus allen Wörtern, die mit x oder y starten, mit x oder y enden und die immer abwechselnd einen Buchstaben und einen Bindestrich enthalten, also z.B. x, y, y-y, x-y-y-x-x-y-y Erstellen Sie eine Grammatik, die L beschreibt. Lösung
Aufgabe 12:
Bearbeiten Sie die Aufgabe III 1. aus dem Abitur 2019. Hier die Lösung auf den Seiten des Rupprecht-Gymnasiums.