Automat

Wenn du an einen Getränkeautomaten, einen Login-Bildschirm oder ein Spielmenü denkst, passiert immer etwas Ähnliches: Es gibt einen aktuellen Zustand, eine Eingabe und danach einen nächsten Zustand. Genau diese Idee greift die Informatik heraus und hält sie bewusst klein und übersichtlich. Danach kannst du Automaten lesen, einfache Automaten selbst beschreiben und prüfen, ob eine Eingabe akzeptiert wird.

Deine Lernziele

• Ich kann erklären, was ein Automat in der Informatik modelliert.
• Ich kann Zustände, Eingaben, Startzustand, Übergänge und Endzustände unterscheiden.
• Ich kann ein kleines Zustandsdiagramm als Tabelle lesen.
• Ich kann entscheiden, ob ein endlicher Automat ein Wort akzeptiert.
• Ich kann deterministische, nichtdeterministische und ausgebende Automaten grob unterscheiden.

Die Grundidee: Zustand plus Eingabe

Ein Automat in der Informatik ist kein Roboter mit Metallarmen. Er ist ein Modell für ein System, das Schritt für Schritt auf Eingaben reagiert. Das Modell lässt alles weg, was gerade nicht wichtig ist, damit du das Verhalten untersuchen kannst.

Definition

Automat

Ein Automat ist ein abstraktes Modell eines Systems. Er befindet sich in einem Zustand, liest Eingaben und wechselt nach festen Regeln in neue Zustände. Die Regeln heißen Übergänge oder Transitionen.

Der wichtigste Gedanke ist: Ein Automat merkt sich nicht unbedingt die ganze Vergangenheit. Er merkt sich das, was im aktuellen Zustand steckt. Wenn die nächste Eingabe kommt, reicht oft dieser Zustand aus, um den nächsten Schritt zu bestimmen.

Beispiel

Ein sehr einfacher Tür-Automat hat zwei Zustände:

• zu
• offen

Die Eingaben heißen druecken und ziehen.

Regeln:

• Im Zustand zu führt druecken zum Zustand offen.
• Im Zustand offen führt ziehen zum Zustand zu.
• Die jeweils andere Eingabe ändert nichts.

Wenn die Tür mit zu startet und die Eingaben druecken, ziehen, ziehen kommen, passiert:

1. zu mit druecken wird offen.
2. offen mit ziehen wird zu.
3. zu mit ziehen bleibt zu.

Der Endzustand ist also zu.

Merke

Ein Automat beantwortet immer wieder dieselbe Frage: In welchem Zustand bin ich gerade, welche Eingabe kommt, und in welchen Zustand gehe ich danach?

Endliche Automaten und das 5-Tupel

In der Schule geht es besonders oft um endliche Automaten. Endlich bedeutet hier: Die Menge der Zustände ist begrenzt. Der Automat kann also nicht beliebig viele verschiedene Zustände neu erfinden.

Definition

Endlicher Automat

Ein endlicher Automat besteht aus endlich vielen Zuständen, einem Eingabealphabet, einem Startzustand, einer Übergangsfunktion und einer Menge von Endzuständen. Oft schreibt man ihn als 5-Tupel \(A=(Q,\Sigma,\delta,q_0,F)\).

Die fünf Teile haben feste Aufgaben:

• \(Q\) ist die Menge aller Zustände.
• \(\Sigma\) ist das Eingabealphabet, also die erlaubten Zeichen.
• \(\delta\) ist die Übergangsfunktion. Sie sagt: aus Zustand und Eingabe wird ein Folgezustand.
• \(q_0\) ist der Startzustand.
• \(F\) ist die Menge der akzeptierenden Endzustände.

Beispiel

Ein Automat soll Wörter über dem Alphabet \(\{0,1\}\) akzeptieren, wenn sie auf 1 enden.

Zustände:

• q0: Das bisher gelesene Wort endet nicht auf 1 oder es wurde noch nichts gelesen.
• q1: Das bisher gelesene Wort endet auf 1.

Startzustand: q0

Endzustand: q1

Übergänge:

• Von q0 mit 0 nach q0
• Von q0 mit 1 nach q1
• Von q1 mit 0 nach q0
• Von q1 mit 1 nach q1

Für das Wort 101 läuft der Automat so:

1. Start in q0
2. Eingabe 1: Wechsel nach q1
3. Eingabe 0: Wechsel nach q0
4. Eingabe 1: Wechsel nach q1

Der Automat endet in q1. Weil q1 ein Endzustand ist, wird 101 akzeptiert.

Diagramm, Tabelle und vollständige Übergänge

Endliche Automaten werden oft als Zustandsdiagramm gezeichnet. Kreise sind Zustände. Ein Pfeil zeigt einen Übergang. Ein Pfeil ohne vorherigen Zustand markiert den Startzustand. Ein doppelt gezeichneter Kreis markiert einen akzeptierenden Endzustand.

Definition

Übergangsfunktion

Die Übergangsfunktion \(\delta\) ordnet einem aktuellen Zustand und einem Eingabezeichen den nächsten Zustand zu. Man schreibt zum Beispiel \(\delta(q_0,1)=q_1\).

Statt eines Diagramms kannst du dieselben Informationen als Tabelle lesen. Für den Automaten "endet auf 1" sieht das so aus:

Zustand	Eingabe 0	Eingabe 1
q0	q0	q1
q1	q0	q1

Jede Zelle beantwortet eine Übergangsfrage. In der Zeile steht der aktuelle Zustand, in der Spalte die Eingabe, in der Zelle der Folgezustand.

Beispiel

Prüfe das Wort 0110 mit der Tabelle.

1. Start: q0
2. 0: Tabelle sagt von q0 mit 0 nach q0
3. 1: von q0 mit 1 nach q1
4. 1: von q1 mit 1 nach q1
5. 0: von q1 mit 0 nach q0

Der Lauf endet in q0. Das Wort wird abgelehnt, denn es endet nicht auf 1.

Gut zu wissen

Manchmal fehlt in einem Diagramm ein Pfeil für eine Eingabe. Für viele Schulaufgaben ergänzt man dann einen Fehlerzustand. Er bedeutet: Ab hier kann das Wort nicht mehr akzeptiert werden, egal welche Zeichen noch kommen.

Akzeptoren und Sprachen

Ein Automat kann benutzt werden, um Wörter zu erkennen. Dann nennt man ihn einen Akzeptor. Er gibt nicht unbedingt etwas Sichtbares aus. Er entscheidet nur: Wort gehört zur Sprache oder Wort gehört nicht zur Sprache.

Definition

Formale Sprache

Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet. Bei Automaten meint "Wort" eine endliche Folge von Zeichen, zum Beispiel 1010 über dem Alphabet \(\{0,1\}\).

Wenn ein Automat \(A\) genau die Wörter akzeptiert, die zu einer Sprache gehören, schreibt man oft \(L(A)\) für die von \(A\) akzeptierte Sprache.

Beispiel

Der Automat aus dem vorherigen Abschnitt akzeptiert genau die Sprache:

Alle Wörter über \(\{0,1\}\), die auf 1 enden.

Beispiele, die akzeptiert werden:

• 1
• 01
• 101
• 111

Beispiele, die abgelehnt werden:

• leeres Wort
• 0
• 10
• 1100

Du musst dafür nicht alle möglichen Wörter auflisten. Der Automat beschreibt die Regel mit Zuständen und Übergängen.

Merke

Ein Akzeptor erkennt eine Sprache, indem er nach dem letzten Zeichen prüft: Endzustand erreicht oder nicht?

Deterministisch, nichtdeterministisch und mit Ausgabe

Bisher war der nächste Zustand immer eindeutig. Solche Automaten heißen deterministisch. In anderen Modellen dürfen mehrere Übergänge für dieselbe Situation möglich sein.

Definition

Deterministischer Automat

Ein deterministischer Automat hat für jede erlaubte Kombination aus aktuellem Zustand und Eingabe höchstens einen eindeutig festgelegten Folgezustand. In vielen Schulaufgaben macht man die Übergangsfunktion vollständig; dann gibt es für jede erlaubte Kombination genau einen Folgezustand.

Definition

Nichtdeterministischer Automat

Ein nichtdeterministischer Automat darf für dieselbe Kombination aus Zustand und Eingabe mehrere mögliche Folgezustände haben. Ein Wort wird akzeptiert, wenn mindestens ein möglicher Lauf in einem akzeptierenden Endzustand endet.

Nichtdeterminismus bedeutet nicht Zufall. Der Automat würfelt keine Wahrscheinlichkeit aus. Er beschreibt mehrere mögliche Wege. Das ist nützlich, wenn man eine Idee einfacher modellieren will.

Beispiel

Stell dir einen Automaten vor, der Wörter akzeptieren soll, in denen irgendwo die Folge ab vorkommt.

Deterministisch kann er sich merken:

• Noch kein passendes a gesehen.
• Gerade ein mögliches a gesehen.
• ab wurde gefunden.

Nichtdeterministisch kann man die Idee oft kürzer beschreiben: Bei jedem gelesenen a darf ein möglicher Lauf sagen: "Vielleicht startet hier die gesuchte Folge." Wenn danach b kommt, erreicht dieser Lauf den Fund-Zustand. Dieser Zustand bleibt bei weiteren Zeichen akzeptierend, damit auch Wörter wie zabz bis zum Wortende angenommen werden.

Gut zu wissen

Automaten können auch Ausgaben haben. Bei einem Mealy-Automaten hängt die Ausgabe von Zustand und Eingabe ab. Bei einem Moore-Automaten hängt die Ausgabe nur vom aktuellen Zustand ab.

Automatenklassen und wofür man sie braucht

Endliche Automaten sind nur eine Automatenklasse. In der theoretischen Informatik vergleicht man Automaten danach, wie viel Speicher und Rechenmacht sie haben.

Definition

Automatenmodell

Ein Automatenmodell legt fest, welche Bauteile ein Automat haben darf: zum Beispiel nur endlich viele Zustände, zusätzlich einen Stapel oder ein Band zum Lesen und Schreiben.

Wichtige Modelle sind:

• Endlicher Automat: endlich viele Zustände, kein zusätzlicher unbegrenzter Speicher.
• Kellerautomat: zusätzlich ein Stapel, auf dem Zeichen abgelegt und wieder heruntergenommen werden können.
• Turingmaschine: ein theoretisch unbegrenztes Band mit Schreib-Lese-Kopf.

Diese Modelle passen zu unterschiedlichen Sprach- und Grammatikklassen. Endliche Automaten erkennen genau die regulären Sprachen; zu ihnen passen reguläre Grammatiken. Kellerautomaten passen zu kontextfreien Sprachen, und Turingmaschinen beschreiben die allgemeinste Stufe im üblichen Schulüberblick.

Definition

Reguläre Grammatik

Eine reguläre Grammatik erzeugt Wörter mit sehr einfachen Produktionsregeln. Zu jedem endlichen Automaten kann man eine passende reguläre Grammatik bauen, die dieselbe Sprache beschreibt, und umgekehrt.

Beispiel

Warum reicht ein endlicher Automat nicht für jede Aufgabe?

Die Sprache \(a^n b^n\) besteht aus Wörtern mit erst mehreren a und danach genauso vielen b, zum Beispiel ab, aabb oder aaabbb. Ein endlicher Automat kann nicht für beliebig große Wörter zählen, wie viele a noch durch b ausgeglichen werden müssen. Ein Kellerautomat kann dagegen für jedes gelesene a ein Zeichen auf den Stapel legen und für jedes spätere b wieder eines herunternehmen.

Die gleiche Stapelidee hilft auch bei Klammerprüfungen in Programmiersprachen.

Merke

Mehr Speicher macht ein Automatenmodell mächtiger, aber nicht automatisch einfacher. Für viele praktische Muster reichen endliche Automaten gerade deshalb, weil sie klein und schnell sind.

Prüfungsmodus

In Aufgaben musst du meistens nicht nur Begriffe wiedergeben. Du sollst einen Lauf ausführen, einen fehlenden Übergang finden, eine Sprache beschreiben oder einen eigenen Automaten entwerfen.

Beispiel

Aufgabe: Ein Automat über \(\{0,1\}\) soll alle Wörter akzeptieren, die eine gerade Anzahl von 1 enthalten.

Idee:

• Zustand gerade: Bisher wurden 0, 2, 4, ... Einsen gelesen.
• Zustand ungerade: Bisher wurden 1, 3, 5, ... Einsen gelesen.
• Startzustand: gerade, weil am Anfang 0 Einsen gelesen wurden.
• Endzustand: gerade.
• Eingabe 0 ändert die Anzahl der Einsen nicht.
• Eingabe 1 wechselt zwischen gerade und ungerade.

Probe mit 1011:

1. Start gerade
2. 1 führt zu ungerade
3. 0 bleibt ungerade
4. 1 führt zu gerade
5. 1 führt zu ungerade

Der Lauf endet in ungerade, also wird 1011 abgelehnt. Das passt, denn es enthält drei Einsen.

Alles auf einen Blick

Merke

Wenn du bei Automaten unsicher bist, gehe langsam vor: Startzustand notieren, Eingabe Zeichen für Zeichen lesen, Übergang anwenden, am Ende Endzustand prüfen.

Abschluss-Check

Jetzt prüfst du die Idee mit neuen Situationen. Hier geht es nicht um neue Begriffe, sondern um Transfer.

Zusammenfassung

Ein Automat ist ein Modell für schrittweises Verhalten. Er hat Zustände, liest Eingaben und folgt Übergangsregeln. Beim endlichen Automaten sind die Zustände endlich viele, und ein Akzeptor entscheidet über Endzustände, ob ein Wort zu einer formalen Sprache gehört.

Deterministische Automaten haben eindeutige Folgezustände. Nichtdeterministische Automaten beschreiben mehrere mögliche Wege, aber keinen Zufall. Automaten mit Ausgabe wie Mealy- und Moore-Automaten modellieren zusätzlich, wann eine Ausgabe entsteht. Für Prüfungsaufgaben hilft dir immer derselbe Ablauf: Startzustand setzen, Eingabe Schritt für Schritt verarbeiten, Endzustand prüfen und die erkannte Sprache als Regel formulieren.