Anmerkung: In dieser Jahrgangsstufe geht es vor allem um die Programmierung mit Java. Zum Erlernen eignet sich unter anderem das Programm BlueJ.
Inhaltsverzeichnis
[Anzeigen]
[Verbergen]
Endliche Automaten
Einführung
Programme können in Zustandsdiagrammen dargestellt werden. Darin werden Übergänge und Aktionen dargestellt. Wird eine Aktion zeitgleich mit dem Übergang gestartet, spricht man von ausgelösten Aktionen.
Die verschiedenen Aktionen führen wiederum zu verschiedenen Zuständen. Ist die Anzahl der Zustände begrenzt, also endlich, spricht man von einem endlichen Automat. Mithilfe eines solchen endlichen Automaten lassen sich viele (aber nicht alle) Systeme modellieren.
Ein endlicher Automat ist eine Art „Black Box“. Befindet sich diese Black Box nach Abarbeitung der Eingabefolge in einem ausgezeichneten Zustand, dem sogenannten Endzustand, so handelt es sich um eine akzeptierte Folge, ansonsten hat sie die Eingabe nicht akzeptiert.
Beispiel: Schwimmbadautomat
Der Eintritt in ein Schwimmbad kostet 2€. Nach Eingabe von Münzen im Gesamtwert von mindestens 2€ öffnet der Automat die Schranke, sonst nicht. Er akzeptiert lediglich Münzen im Wert von 0,50€, 1€ und 2€.
Das zugehörige Zustandsdiagramm sieht so aus, wobei q Zustand beschreibt:
Zustandsübergangstabelle
Das Zustandsdiagramm lässt sich auch tabellarisch darstellen. Diese Tabelle wird als Zustandsübergangstabelle bezeichnet. Hierbei steht in der Kopfzeile die Aktion, die den Übergang auslöst, in der linken Spalte der Aggregatszustand des Übergangs und in der Zelle die ausgelöste Aktion sowie den Zielüberstand des Übergangs[1]Informatik 3, S. 83..
Beim Schwimmbadautomaten sähe die Tabelle etwa wie folgt aus:
| 0,5 | 1,0 | 2,0 | |
| start | q0,5 | q1 | q2 |
| q0,5 | q1 | q1,5 | q2 |
| q1 | q1,5 | q2 | q2 |
| q1,5 | q2 | q2 | q2 |
| q2 | q2 | q2 | q2 |
Häufig werden in der Informatik „Wörter“ als Zeichenketten (häufig nur Zeichen a und b) oder auch „Zahlen“ als Ziffernketten eingegeben und daraufhin untersucht, ob sie eine bestimmte Bedingung erfüllen.
Implementierung von endlichen Automaten
Endliche Automaten werden durch ein spezielles Objekt implementiert. Dabei wird der Zustand des Objekts durch eine konkrete Kombination der Attributswerte definiert. Häufig werden allerdings nicht alle Attributswerte benötigt. Aus diesem Grund kann ein spezieller Zustand verwendet werden, dessen Wert den Zustand des simulierten Automaten beschreibt[2]Informatik 3, S. 83..