Einführung in die Automatentheorie und JFLAP

Definition: Abstrakte Maschine und Automat

Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Die Vereinfachung der Fähigkeiten erlaubt es, das Verhalten eines Automaten leichter zu verstehen und zu vergleichen – darauf kommt es an.

Grundlegendes Verhalten

Das grundsätzliche Verhalten eines Automaten ist immer gleich: Dem Automaten wird von außen eine Eingabe als Folge von Zeichen vorgelegt. Der Automat befindet sich in einem Zustand. Jedes Mal, wenn ein Eingabezeichen eintrifft, kann sich abhängig vom Eingabezeichen und dem gegenwärtigen Zustand ein neuer Zustand, der Folgezustand, einstellen (Zustandsübergang oder Transition). Die Menge der möglichen Zustandsübergänge, die das Verhalten des Automaten definiert, kann als das Programm des Automaten verstanden werden.

Elemente des Automaten

• Übergänge (Transitionen): Werden anhand einer Übergangsfunktion beschrieben. Diese Funktion gibt an, mit welchem Zeichen von einem bestimmten Zustand in einen anderen gewechselt werden kann.
• Pfeile: Visualisieren den Wechsel von einem Zustand in den anderen.
• Zustand (q): Zu jedem Zeitpunkt befindet sich ein Automat in genau einem Zustand (q).
• Startzustand: Wird durch einen Pfeil mit der Beschriftung „Start“ gekennzeichnet.
• Endzustand: Wird durch einen doppelten Kreis dargestellt. Ein Automat kann mehrere Endzustände haben.

Ablauf und Eingabe

Reagieren

Der Automat sucht einen Übergang, der vom aktuellen Zustand ausgeht und mit der Aktion, die an der Reihe ist, beschriftet ist.

Eingabe

Die Eingabe ist eine Folge von Aktionen. Ein Automat betrachtet die einzelnen Aktionen der Reihe nach und reagiert entsprechend. Dies können Folgen von Zahlen, Wörtern, Zeichen oder Buchstaben sein, aber in realen Automaten auch physische Aktionen (z. B. Knöpfe, Münzen, Auswahltasten).

Akzeptanz und Sprache

Eingabealphabet

Die Menge an Zeichen, Wörtern oder Symbolen, auf die der Automat reagieren kann.

Wort

Eine Zeichenkette, die aus beliebigen Zeichen des Eingabealphabets besteht.

Akzeptanzverhalten

Der Automat akzeptiert das Eingabewort genau dann, wenn er sich nach dem Einlesen des ganzen Wortes in einem Endzustand befindet. Ansonsten akzeptiert er das Wort nicht. Man sagt auch, der Automat verwirft in diesem Fall das Eingabewort.

Sprache eines Automaten

Die Menge von Wörtern, die der Automat akzeptiert. Man sagt, der Automat erkennt diese Sprache.

Exkurs: Binärsystem

Binärdarstellung (Beispiel): 11011 = 1·2⁰ + 1·2¹ + 0·2² + 1·2³ + 1·2⁴ = 1 + 2 + 0 + 8 + 16 = 27.

Automatenerstellung mit JFLAP

1. Zustände setzen

   Gehe in den Modus Zustand setzen, indem du auf den Kreis-Button klickst. Nun kannst du beliebig viele Zustände per Mausklick setzen.

2. Übergänge setzen

   Gehe in den Modus Übergänge setzen, indem du auf den länglichen Pfeil-Button klickst. Verbinde nun die entsprechenden Zustände, indem du einen Zustand anklickst, die Maustaste gedrückt hältst und beim Zielzustand wieder loslässt. So kannst du auch einen Übergang von einem Zustand zu sich selbst setzen.

3. Zustände oder Übergänge löschen

   Gehe in den Modus Löschen, indem du auf den Totenkopf-Button klickst. Jetzt kannst du die Zustände oder Übergänge anklicken, die du löschen willst.

4. Zustände bearbeiten (Start- und Endzustand)

   Klickt man einen Zustand mit der rechten Maustaste an, wird ein Menü angezeigt. Bei weiterhin gedrückter rechter Maustaste können z. B. folgende Menüpunkte gewählt werden:

   • Final: Endzustand setzen
   • Initial: Anfangszustand setzen

5. Speichern

   Über den Menüpunkt File > Save as ... kann man das Modell speichern.