JFLAP – eigene Automaten entwerfen

Nachdem du jetzt schon fertige Automaten mit JFLAP testen kannst, wirst du nun lernen, auch eigene Automaten mit der Software zu entwickeln. Vollziehe hierzu zunächst wieder die Schritte des Beispiels nach.

Der Automat, den du erstellst, hat als Eingabealphabet die Menge {0}. Er soll vorerst nur das Wort 00 erkennen.

Öffne JFLAP, Finite State Automaton.

Nun erscheint wieder das Fenster, in dem du einen Automaten modellieren kannst. Links oben siehst du mehrere Symbole. Einen Mauspfeil, einen Kreis mit einem eingezeichneten Mittelpunkt, einen langgezogenen Pfeil und einen Totenkopf. Jedes der Symbole stellt einen bestimmten Modus dar.

Wenn du mit der linken Maustaste den Kreis anklickst, bist du in dem Modus, in dem Zustände erzeugt werden können.

Gehe nun zuerst auf diesen Kreis, um in den Modus Zustand setzen zu wechseln. Gehe dann auf die weiße Zeichenfläche und klicke auf die linke Maustaste. Schon ist der erste Zustand erzeugt, der mit q0 bezeichnet wird. Setze rechts daneben noch drei weitere Zustände, so dass du schließlich q0 bis q3 gesetzt hast.

Eigentlich benötigst du aber nur die Zustände q0 und q1. Wechsle deshalb in den Lösch-Modus, indem du den Totenkopf anklickst. Nun kannst du die überflüssigen Zustände q2 und q3 durch Anklicken löschen.

Jetzt fehlen noch die Übergänge. Um diese zu zeichnen, musst du in den Modus Übergänge setzen gehen, indem du den länglichen Pfeil anklickst. Setze einen Übergang von q0 zu q1, indem du den Zustand q0 anklickst und die linke Maustaste gedrückt hältst. Ziehe dann die Maus zum Zustand q1 und lasse erst dann die gedrückte Maustaste wieder los. Es erscheint ein Eingabefeld. Klicke dieses an, schreibe eine 0 hinein und drücke Enter.

Damit ist dein Übergang gesetzt. Setze analog auch noch den zweiten Übergang. Falls du irrtümlich einen falschen Übergang setzt, kannst du diesen auch löschen, indem du in den Lösch-Modus wechselst und den entsprechenden Übergang anklickst.

Möchtest du einen Übergang von einem Zustand zu einem anderen, der mit mehreren Symbolen beschriftet ist, machen, kannst du einfach mehrere Übergänge zwischen den beiden Zuständen erzeugen und jeden dieser Übergänge mit einem Symbol beschriften. Nun kannst du den Automaten noch etwas mehr in die Mitte verschieben. Wechsle dazu in den Modus normal. Nun kannst du die Zustände anklicken, und während du die Maustaste gedrückt hältst, verschieben.

Dieser Modus hat noch eine weitere Eigenschaft: Wenn du dich bei der Beschriftung verschrieben hast, kannst du diese in diesem Zustand anklicken und erneut beschriften.

Außerdem kannst du in dem Modus normal festlegen, dass q0 dein Anfangszustand sein soll. Klicke dazu mit der rechten Maustaste auf q0. Es erscheint ein Menü. Wähle Initial (deutsch: Anfangs-) aus. Auf q0 zeigt jetzt ein großer Pfeil. Analog klickst du nun mit der rechten Maustaste auf q2 und markierst diesen als Endzustand, indem du im Menü auf Final (deutsch: End-) klickst. Schon ist dein erster Automat mit JFLAP fertig und kann getestet werden.

Hier noch einmal ein kurzer Überblick über die verschiedenen Funktionen von JFLAP.

• Zustände setzen: Gehe in den Modus Zustand setzen, indem du den Kreisbutton anklickst. Dann kannst du beliebig viele Zustände per Mausklick setzen.
• Übergänge setzen: In den Modus Übergänge setzen gelangst du, indem du den Button mit dem länglichen Pfeil anklickst. Dann kannst du den Zustand, von dem der Übergang ausgehen soll, anklicken und die Maustaste gedrückt halten. Lass sie erst wieder los, wenn du am Zielzustand angelangt bist. So kannst du auch einen Übergang von einem Zustand zu sich selbst setzen.
• Zustände/Übergänge löschen: In den Lösch-Modus kommst du, indem du den Totenkopf-Button anklickst. In diesem Modus kannst du die Zustände/Übergänge anklicken, die du löschen willst.
• Zustände bearbeiten: Klickt man einen Zustand mit der rechten Maustaste an, wird ein Menü angezeigt. Bei weiterhin gedrückter rechter Maustaste können z. B. die folgenden Menüpunkte ausgewählt werden:
  • Initial: Anfangszustand setzen
  • Final: Endzustand setzen
• Über den Menüpunkt File→Save as kann das Modell gespeichert werden.

Beschäftige dich noch einmal mit dem Schulausflug-Automaten. Lade dir zuerst erneut den Automaten „Schulausflug“ in dein JFLAP-Programm. Wie du bereits weißt, wollen Anke und Anne auch an dem Ausflug teilnehmen. Ändere den Automaten deshalb so ab, dass er auch Anke und Anne akzeptiert!

Erstelle mit JFLAP einen Automaten, der überprüft, ob eine beliebig lange Telefonnummer mit einer Stuttgarter Vorwahl beginnt (0711).

Stell dir vor, du spielst Schach gegen den Computer und musst die Schachpartie unterbrechen, bevor sie zu Ende gespielt ist. Was tun, bevor der Computer heruntergefahren wird?

Viele Schachprogramme stellen eine Speicherfunktion zur Verfügung, mit der man den aktuellen Spielzustand sichern kann.

Häufig wird dabei die sogenannte Forsyth-Edwards-Notation (kurz: FEN) verwendet, um Schachspielzustände zu beschreiben. Sie erstellen eine Datei, in der der Spielzustand mit einer Zeichenfolge beschrieben wird. Im Fall des oben gezeigten Spielzustands erhält man folgende auf den ersten Blick etwas kryptische Zeichenfolge:

 rnbqkb1r/pp1p1ppp/2p2n2/8/2P1p3/2N2NP1/PP1PPP1P/R1BQKB1R w KQkq - 0 5

(i) Versuche erst einmal, diese Zeichenfolge zu verstehen. Auf der Seite Wikipedia - Forsyth-Edwards-Notation findest du Hilfen.

(ii) Wir betrachten im Folgenden nur den ersten Teil einer solchen FEN-Darstellung eines Schachspielzustands. Dieser Teil beschreibt die aktuelle Spielbrettbelegung.

rnbqkb1r/pp1p1ppp/2p2n2/8/2P1p3/2N2NP1/PP1PPP1P/R1BQKB1R

• Welche Zeichen dürfen in einer FEN-Beschreibung der Spielbrettbelegung vorkommen?
• Betrachte die folgende Tabelle, in der Beispiele mit korrekt bzw. nicht korrekt gebildeten FEN-Beschreibung einer Spielbrettbelegung gesammelt sind. Vervollständige die Tabelle.

• Erläutere, dass man die FEN-Beschreibung von Spielbrettbelegungen als fendlichen Automaten beschreiben kann. Verwende hierzu die Begiffe „Alphabet“, „Wort“, „Eingabe“ im diesem Kontext.
• Erstelle einen Automaten mit JFLAP, der durch sein Akzeptanzverhalten die Eingabe eines Spielzustands in der FEN-Schreibweise auf Korrektheit überprüft.