Endlicher Automat

Ein endlicher Automat ist ein Modell eines Systems mit diskreten Ein- und Ausgaben und einer endlichen Anzahl von Zuständen.

Als Beispiel gucken wir uns eine Lampe mit Schalter an:

Beispiel: Lichtschalter

Die Lampe hat zwei Zustände: «Licht aus» und «Licht ein».

Je nachdem in welchem Zustand sich die Lampe befindet, kann ich durch Drücken des Schalters das Licht ein- oder ausschalten.

Das Schalter-Drücken ändert also den Zustand der Lampe. Wir sprechen von einem Zustandsübergang.

Zustandsübergangsdiagramm

Diese Übergänge zwischen den Zuständen kann man in einem Diagramm darstellen:

Die Zustände werden durch Kreise gekennzeichnet und benannt. Die Übergänge werden durch benannte Pfeile dargestellt.

Das obige Diagramm lässt sich wie folgt lesen:

Zu Beginn ist das Licht aus. Wenn ich den Schalter drücke, geht das Licht an. Wenn ich den Schalter nochmals drücke, geht es wieder aus.

Zustandsübergangstabelle

Dieser Sachverhalt lässt sich auch in einer Tabelle darstellen:

Lichtschalter

δ	drücken
Licht aus	Licht ein
Licht ein	Licht aus

Die Tabelle wird wie folgt interpretiert:

Zustände

Für jeden Zustand gibt es eine Zeile.

Dessen Name steht in der ersten Spalte (gekennzeichnet durch den griechischen Buchstaben Delta δ)

Übergänge

Für jeden Übergang gibt es eine Spalte

Der Name des Übergangs steht in der Kopfzeile

Kann ein Zustand mit diesem Übergang in einen anderen Zustand überführt werden, so steht in der entsprechenden Zeile der neue Zustand. (sonst bleibt der Eintrag leer)

Beispiel: Tabelle lesen

Wir können die Tabelle wie folgt lesen:

• Wenn das Licht aus ist (1. Zeile, Spalte δ), dann bewirkt ein drücken des Schalters einen Zustandswechsel zum Zustand Licht ein.
• Wenn das Licht ein ist (2. Zeile, Spalte δ), dann bewirkt ein drücken des Schalters einen Zustandswechsel zum Zustand Licht aus.

So würde die Zustandssübergangstabelle eines Lichtschalters mit Timer aussehen:

Lichtschalter mit Timer

δ	drücken	Timer läuft ab
Licht aus	Licht ein
Licht ein		Licht aus

Aufgabe: Lichtschalter mit Timer

Interpretiere die Tabelle schriftlich (siehe Beispiel oberhalb) und erstelle ein passendes Zustandsübergangsdiagramm.

Lösung: Lichtschalter mit Timer (nicht angemeldet)

Diese Lösung ist nur für angemeldete Benutzer zugänglich – wenn die LK die Lösung freigegeben hat. Bitte melde dich an, um die Lösung einsehen zu können.

Aufgabe: Lichtschalter und Timer

Wie müsste man die Tabelle anpassen, damit das Licht nicht nur nach Ablauf des Timers, sondern auch mit dem Schalter ausgeschaltet werden könnte?

Beschreibe die Anpassungen der Tabelle und Zeichne ein Zustandsübergangsdiagramm.

Lösung: Lichtschalter und Timer (nicht angemeldet)

Diese Lösung ist nur für angemeldete Benutzer zugänglich – wenn die LK die Lösung freigegeben hat. Bitte melde dich an, um die Lösung einsehen zu können.

weitere Beispiele und Aufgaben

Wir können nun andere Abläufe mittels endlichen Automaten formulieren:

Getränkeautomat

Ein Getränkeautomat, wie er in der Eingangshalle des Gymers steht, aber etwas vereinfacht:

• akzeptiert nur Ein- und Zweifränkler
• liefert nur Sprite oder Cola
• beides kostet 3.-

Man soll also mit Ein- und Zweifränkler den Automat «füttern». Sobald 3.- erreicht sind, kann man ein Getränk rauslassen.

Wir überlegen uns zuerst welche Zustände und Übergänge es braucht:

Zustände

der Automat muss sich den Betrag merken – er soll ja nur bei 3.- ein Getränk rauslassen

Es gibt also 4 Zustände: 0.-, 1.-, 2.- oder 3.-
Je nachdem wie viel Geld wir reingesteckt haben.

Übergänge

Je nach Zustand kann man Ein- oder Zweifränkler füttern, oder eine der beiden Getränketasten drücken

Daraus ergibt sich das folgende Übergangsdiagramm:

Getränkeautomat

Wir beginnen im Zustand 0.-. Man kann den Automaten mit einem Ein- oder Zweifränkler füttern. So kommt man also in den Zustand 1.- oder 2.-. Nun kann man ihn weiterfüttern, bis der Zustand 3.- erreicht wird. Nur in diesem Zustand reagiert der Automat auf die Getränketaste indem er das Getränk rauslässt und in den End-Zustand 0.- wechselt

δ	1.-	2.-	sprite	coke
0.-	1.-	2.-
1.-	2.-	3.-
2.-	3.-
3.-			0.-	0.-

Videogerät

Ein Videogerät kann auch als endlicher Automat angesehen werden:

Videogerät

Aufgabe: Videogerät

Erstelle eine Zustandsübergangstabelle für das Videogerät, indem du das obenstehende Diagramm genau ansiehst und es dann in eine Tabelle übersetzt.

Lösung: Videogerät (nicht angemeldet)

Diese Lösung ist nur für angemeldete Benutzer zugänglich – wenn die LK die Lösung freigegeben hat. Bitte melde dich an, um die Lösung einsehen zu können.

⭐ Zusatzaufgabe: weitere Aufgaben

Erstelle Zustandsübergangsdiagramme und -tabellen für die folgenden beiden Automaten:

• Stoppuhr
• ferngesteuertes Garagentor