Anmerkung: In dieser Jahrgangsstufe geht es vor allem um die Programmierung mit Java. Zum Erlernen eignet sich unter anderem das Programm BlueJ.
Endliche Automaten
Ein endlicher Automat ist eine Art „Black Box“, in die wir etwas eingeben können und der je nach Eingabe in verschiedene Zustände übergeht. Befindet sich die 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 einen Zustand beschreibt:
Die dazugehörige Zustandsübergangstabelle sieht 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.