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 ÜbergangEin 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.
BeispielEin Kugelschreiber mit Druckknopf. Welche Zustände hat er, welche Eingaben gibt es, und was bewirken sie?
Endlich heisst endlichWir 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.
BeispielDie Tür eines Busses. Sie ist gesperrt (), bis der Fahrer sie freigibt (); dann kann ein Fahrgast den Taster drücken und die Tür geht auf (). 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) unds(Tür schliesst).Tragen Sie die Übergänge in die Tabelle ein.
fxtsgesperrt freigegeben offen Die leeren Felder sind kein Versehen: im Zustand etwa bewirkt der Taster nichts, weil die Tür schon offen ist.
1.3 Aufgaben zu Zuständen und Diagrammen
Aufgabe 1.3.1Ein 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.2Gegeben ist die folgende Übergangstabelle über dem Eingabealphabet . Startzustand ist .
ab(a) Zeichnen Sie das zugehörige Zustandsdiagramm.
(b) Bestimmen Sie die Zustandsfolge bei der Eingabe
a b a a b a aund geben Sie den Zustand am Schluss an.
Aufgabe 1.3.3Füllen Sie zum folgenden Zustandsdiagramm die Übergangstabelle aus und beschreiben Sie in einem Satz, woran man erkennt, dass der Automat den Zustand nie wieder verlässt.
![]()
01
SenkeEin 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 AutomatEin endlicher Automat besteht aus vier Teilen:
Die übliche SchreibweiseIn Büchern werden die vier Teile meist zu einem Vierertupel zusammengefasst: für die Zustände, für das Eingabealphabet, für die Übergänge und für den Startzustand. Wir kommen in diesem Skript ohne diese Abkürzungen aus.
BeispielGeben Sie die vier Teile der Bustür an. Die Eingaben sind
f(Fahrer gibt frei),x(Fahrer sperrt),t(Fahrgast drückt den Taster) unds(Tür schliesst).
2.2 Automaten mit Ausgabe
Definition: Mealy-AutomatEin Mealy-Automat gibt bei jedem Übergang ein Zeichen aus. Er hat zwei Teile mehr als ein endlicher Automat:
BeispielEin Getränkeautomat verkauft eine Flasche für zwei Franken. Er nimmt Münzen zu einem und zu zwei Franken und gibt Rückgeld. Zustand heisst «noch nichts eingeworfen», Zustand heisst «ein Franken liegt bereit». Der Strich
-steht für «keine Ausgabe».Welche Ausgabe erzeugt die Eingabefolge
1 1 2 1?
LernvideoMealy-Automat (3:36)
Das Video fasst die Teile eines Automaten zu einem Tupel zusammen und schreibt für die Zustände und für das Eingabealphabet. Gemeint ist dasselbe wie oben.
2.3 Aufgaben zu endlichen Automaten
Aufgabe 2.3.1Geben Sie zum folgenden Automaten die vier Teile an. Schreiben Sie die Übergänge als Liste von Pfeilen. Startzustand ist .
ab
Aufgabe 2.3.2Lesen Sie aus dem folgenden Diagramm ab, in welchem Zustand der Automat landet:
(a) aus nach dem Zeichen
1(b) aus nach dem Zeichen
0(c) aus nach dem Zeichen
1(d) aus nach den beiden Zeichen
1 1
Aufgabe 2.3.3Ein 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.4Ein 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.5Entwerfen Sie einen Mealy-Automaten über dem Eingabealphabet , 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 Eingabe1 0 1 1 0an.
Zusatzaufgabe 2.3.6Ein Zahlenschloss öffnet, sobald die drei Ziffern
1,9,1unmittelbar nacheinander eingegeben werden. Alle anderen Ziffern fasst man zu einem einzigen Eingabezeichenzzusammen, das Eingabealphabet ist also . 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 Eingabe1 1 9 1geschehen soll.