Nach einem Skript von Philipp Moor (Kantonsschule Zimmerberg).

Lernziele
  • Erklären, was ein Zustand und was ein Übergang ist
  • Ein Zustandsdiagramm lesen und zu einer Beschreibung selber zeichnen
  • Zwischen Zustandsdiagramm und Übergangstabelle wechseln
  • Die vier Teile eines endlichen Automaten benennen und zu einem gegebenen Automaten angeben
  • Zu einer Eingabefolge die durchlaufene Zustandsfolge bestimmen
  • Einen Mealy-Automaten mit Ausgabe entwerfen und lesen

1 Zustände, Übergänge, Diagramme

1.1 Der Zustandsbegriff

Definition: Zustand und Übergang

Ein System befindet sich zu jedem Zeitpunkt in genau einem Zustand. Der Zustand fasst alles zusammen, was das System aus seiner Vergangenheit noch wissen muss, um auf die nächste Eingabe richtig zu reagieren. Alles Übrige darf es vergessen.

Eine Eingabe löst einen Übergang von einem Zustand in einen Zustand aus. Der Zustand, in dem das System beginnt, heisst Startzustand.

Beispiel

Ein Kugelschreiber mit Druckknopf. Welche Zustände hat er, welche Eingaben gibt es, und was bewirken sie?

Endlich heisst endlich

Wir betrachten nur Systeme mit endlich vielen Zuständen. Grössen mit beliebig feinen Zwischenwerten, etwa eine Temperatur oder eine Position, lassen sich deshalb nicht direkt als Zustände verwenden. Sie müssen zuerst in endlich viele Bereiche eingeteilt werden, etwa in zu kalt, richtig und zu warm.

1.2 Zustandsdiagramm und Übergangstabelle

Ein Automat lässt sich auf zwei Arten aufschreiben. Im Zustandsdiagramm ist jeder Zustand ein Kreis und jeder Übergang ein Pfeil, an dem die auslösende Eingabe steht; der Startzustand trägt zusätzlich einen Pfeil, der von nirgendwo herkommt. In der Übergangstabelle steht eine Zeile pro Zustand und eine Spalte pro Eingabezeichen, und im Feld steht der Zustand, in den der Automat wechselt. Ein leeres Feld bedeutet, dass diese Eingabe in diesem Zustand nichts bewirkt. Beide Darstellungen enthalten genau dieselbe Information.

Beispiel

Die Tür eines Busses. Sie ist gesperrt (q0q_0), bis der Fahrer sie freigibt (q1q_1); dann kann ein Fahrgast den Taster drücken und die Tür geht auf (q2q_2). Schliesst die Tür wieder, so bleibt sie freigegeben. Der Fahrer kann jederzeit wieder sperren, solange die Tür zu ist. Die Eingaben heissen f (Fahrer gibt frei), x (Fahrer sperrt), t (Fahrgast drückt den Taster) und s (Tür schliesst).

Zustandsdiagramm der BustürZustandsdiagramm der Bustür

Tragen Sie die Übergänge in die Tabelle ein.

fxts
q0q_0 gesperrt
q1q_1 freigegeben
q2q_2 offen

Die leeren Felder sind kein Versehen: im Zustand q2q_2 etwa bewirkt der Taster nichts, weil die Tür schon offen ist.

1.3 Aufgaben zu Zuständen und Diagrammen

Aufgabe 1.3.1

Ein Drehkreuz am Museumseingang ist zunächst gesperrt. Wirft man eine Münze ein, so entriegelt es. Geht eine Person hindurch, so sperrt es wieder. Wirft man eine zweite Münze ein, solange es entriegelt ist, so passiert nichts. Drückt man gegen ein gesperrtes Drehkreuz, so passiert ebenfalls nichts.

(a) Nennen Sie die Zustände und die Eingaben.

(b) Zeichnen Sie das Zustandsdiagramm.

Aufgabe 1.3.2

Gegeben ist die folgende Übergangstabelle über dem Eingabealphabet {a,b}\{\texttt{a}, \texttt{b}\}. Startzustand ist q0q_0.

ab
q0q_0q1q_1q0q_0
q1q_1q2q_2q0q_0
q2q_2q2q_2q0q_0

(a) Zeichnen Sie das zugehörige Zustandsdiagramm.

(b) Bestimmen Sie die Zustandsfolge bei der Eingabe a b a a b a a und geben Sie den Zustand am Schluss an.

Aufgabe 1.3.3

Füllen Sie zum folgenden Zustandsdiagramm die Übergangstabelle aus und beschreiben Sie in einem Satz, woran man erkennt, dass der Automat den Zustand q2q_2 nie wieder verlässt.

Zustandsdiagramm zu Aufgabe 1.3.3Zustandsdiagramm zu Aufgabe 1.3.3
01
q0q_0
q1q_1
q2q_2
Senke

Ein Zustand, den der Automat nie wieder verlässt, heisst Senke, auf Englisch sink. Gebräuchlich sind auch die Bezeichnungen Fangzustand und Falle. Im Diagramm erkennt man eine Senke daran, dass jeder Pfeil, der von ihr wegführt, wieder bei ihr endet. Gerät ein Automat einmal in eine Senke, so steht das Ergebnis fest: alles Weitere in der Eingabe ändert nichts mehr daran.

2 Endliche Automaten

2.1 Die vier Teile eines endlichen Automaten

Definition: endlicher Automat

Ein endlicher Automat besteht aus vier Teilen:

Die übliche Schreibweise

In Büchern werden die vier Teile meist zu einem Vierertupel A=(Q,Σ,δ,q0)A = (Q, \Sigma, \delta, q_0) zusammengefasst: QQ für die Zustände, Σ\Sigma für das Eingabealphabet, δ\delta für die Übergänge und q0q_0 für den Startzustand. Wir kommen in diesem Skript ohne diese Abkürzungen aus.

Beispiel

Geben Sie die vier Teile der Bustür an. Die Eingaben sind f (Fahrer gibt frei), x (Fahrer sperrt), t (Fahrgast drückt den Taster) und s (Tür schliesst).

Zustandsdiagramm der BustürZustandsdiagramm der Bustür

2.2 Automaten mit Ausgabe

Definition: Mealy-Automat

Ein Mealy-Automat gibt bei jedem Übergang ein Zeichen aus. Er hat zwei Teile mehr als ein endlicher Automat:

Beispiel

Ein Getränkeautomat verkauft eine Flasche für zwei Franken. Er nimmt Münzen zu einem und zu zwei Franken und gibt Rückgeld. Zustand z0z_0 heisst «noch nichts eingeworfen», Zustand z1z_1 heisst «ein Franken liegt bereit». Der Strich - steht für «keine Ausgabe».

Mealy-Automat des GetränkeautomatenMealy-Automat des Getränkeautomaten

Welche Ausgabe erzeugt die Eingabefolge 1 1 2 1?

Lernvideo

Das Video fasst die Teile eines Automaten zu einem Tupel zusammen und schreibt ZZ für die Zustände und AA für das Eingabealphabet. Gemeint ist dasselbe wie oben.

2.3 Aufgaben zu endlichen Automaten

Aufgabe 2.3.1

Geben Sie zum folgenden Automaten die vier Teile an. Schreiben Sie die Übergänge als Liste von Pfeilen. Startzustand ist q0q_0.

ab
q0q_0q1q_1q0q_0
q1q_1q2q_2q0q_0
q2q_2q2q_2q0q_0
Aufgabe 2.3.2

Lesen Sie aus dem folgenden Diagramm ab, in welchem Zustand der Automat landet:

(a) aus q0q_0 nach dem Zeichen 1

(b) aus q1q_1 nach dem Zeichen 0

(c) aus q2q_2 nach dem Zeichen 1

(d) aus q0q_0 nach den beiden Zeichen 1 1

Zustandsdiagramm zu Aufgabe 2.3.2Zustandsdiagramm zu Aufgabe 2.3.2
Aufgabe 2.3.3

Ein Billettautomat verlangt drei Franken und nimmt Münzen zu einem und zu zwei Franken. Sobald drei Franken oder mehr eingeworfen sind, gibt er das Billett aus und, falls nötig, einen Franken Rückgeld; danach beginnt er von vorn. Zeichnen Sie den Mealy-Automaten mit allen Ein- und Ausgaben.

Aufgabe 2.3.4

Ein Sparautomat soll sich merken, wie viele Münzen insgesamt eingeworfen wurden, und zwar für beliebig grosse Anzahlen. Erklären Sie, warum sich das mit einem endlichen Automaten nicht bauen lässt.

Weitere Aufgaben

Zusatzaufgabe 2.3.5

Entwerfen Sie einen Mealy-Automaten über dem Eingabealphabet {0,1}\{\texttt{0}, \texttt{1}\}, der nach jedem gelesenen Zeichen ausgibt, ob die Anzahl der bisher gelesenen Einsen gerade (g) oder ungerade (u) ist. Zeichnen Sie das Diagramm und geben Sie die Ausgabefolge zur Eingabe 1 0 1 1 0 an.

Zusatzaufgabe 2.3.6

Ein Zahlenschloss öffnet, sobald die drei Ziffern 1, 9, 1 unmittelbar nacheinander eingegeben werden. Alle anderen Ziffern fasst man zu einem einzigen Eingabezeichen z zusammen, das Eingabealphabet ist also {1,9,z}\{\texttt{1}, \texttt{9}, \texttt{z}\}. Der Automat gibt bei jedem Übergang aus, ob das Schloss offen (o) oder zu (-) ist. Zeichnen Sie den Mealy-Automaten. Achten Sie darauf, was nach der Eingabe 1 1 9 1 geschehen soll.