Der Mealy-Automat: Übungen – Informatik Leistungskurs

A1

Gültige Beschriftungen?

AFB I

Ein Mealy-Automat für ein Treppenhauslicht hat das Eingabealphabet Σ = {T, U} (T = Taster gedrückt, U = Uhr abgelaufen) und das Ausgabealphabet Ω = {an, aus}. Ordnen Sie jede Pfeilbeschriftung zu: Ist sie für diesen Automaten korrekt notiert?

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).

1korrekte Beschriftung e / a

2fehlerhaft notiert

Vor dem Schrägstrich steht genau ein Eingabezeichen aus Σ, dahinter ein Wort aus Ω* — auch ein Ausgabewort wie „aus an“ oder ε. Häufigster Fehler: „T“ ohne Ausgabe für korrekt zu halten. Beim Mealy-Automaten fehlt dann die Ausgabe; richtig ist „T / ε“. „U / 0“ ist falsch, weil 0 nicht zu Ω gehört — ε und 0 sind verschieden.

Ansatz: Prüfen Sie zwei Dinge: Steht links ein Zeichen aus Σ, rechts ein Wort aus Ω (oder ε)?

Weiter: Ausgabewörter aus mehreren Zeichen von Ω sind erlaubt, eine fehlende Ausgabe nicht.

A2

Stimmt das? — Mealy-Grundlagen

AFB I

Nennen Sie zu jeder Aussage über Mealy-Automaten, ob sie stimmt.

6 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.

Aussage 1 von 6

Die Kernidee: Die Ausgabe gehört zum Übergang, also zum Paar aus Zustand und Eingabezeichen. Wer sie dem Zustand zuordnet, verwechselt den Mealy-Automaten mit einem Automaten, der Ausgaben in den Zuständen notiert.

Ansatz: Denken Sie an die Beschriftung e / a am Pfeil.

Weiter: ε ist die leere Ausgabe — und Endzustände gibt es beim Mealy-Automaten nicht.

A3

Vom Graphen zur Tabelle

AFB I

Der Treppenhausautomat aus A1 ist hier als Zustandsgraph gegeben.

Treppenhauslicht (Σ = {T, U}, Ω = {an, aus})

Lesen Sie aus dem Graphen jedes Tabellenfeld „Folgezustand / Ausgabe“ ab.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Zustand	T	U
aus
an

Häufigster Fehler: im Feld (an, T) „an / an“ eintragen. Das Licht brennt schon — der Pfeil ist eine Schleife mit „T / ε“. Beachten Sie auch die Reihenfolge im Tabellenfeld: erst Folgezustand, dann Ausgabe. Am Pfeil steht dagegen erst die Eingabe, dann die Ausgabe.

Ansatz: Suchen Sie für jedes Feld den Pfeil, der im Zeilen-Zustand beginnt und die Spalten-Eingabe vor dem Schrägstrich trägt.

Weiter: Bei Schleifen ist der Folgezustand der Zustand selbst.

A4

Begriffe und Bedeutungen

AFB I

Geben Sie zu jedem Begriff bzw. Zeichen des Mealy-Automaten die passende Bedeutung an, indem Sie beide verbinden.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

Σ und Ω werden gern vertauscht: Σ („Sigma“) gehört zur Eingabe wie beim DEA, Ω („Omega“) kommt beim Mealy-Automaten für die Ausgabe hinzu. Und ε ist kein Zeichen aus Ω, sondern das leere Wort.

Ansatz: Σ kennen Sie schon vom DEA — dort gab es nur Eingaben.

Weiter: Das Ausgabewort entsteht, wenn man die Ausgaben aller benutzten Pfeile aneinanderreiht; ε fällt dabei weg.

A5

Ablaufprotokoll: Parkhausschranke

AFB II

Eine Parkhausschranke wird durch einen Mealy-Automaten gesteuert: t = gültiges Ticket eingesteckt, s = Auto hat die Lichtschranke passiert; Ω = {auf, zu, T} mit T = „Ticket zurückgeben“.

Parkhausschranke (Σ = {t, s})

Erstellen Sie das Ablaufprotokoll für die Eingabe t t s s t. „↑“ heißt: Zustand = Folgezustand der Zeile darüber.

Füllen Sie alle Felder aus und prüfen Sie dann (Enter prüft ebenfalls). Leere Ausgabe als ε oder -; Ausgabewort mit Leerzeichen trennen.

Schritt	Zustand	Eingabe
1	zu	t
2	↑	t
3	↑	s
4	↑	s
5	↑	t
Ausgabewort

Folge: zu → offen → offen → zu → zu → offen; Ausgabewort „auf T zu auf“ — fünf Eingaben, aber nur vier Ausgaben, weil Schritt 4 ε ausgibt. Typischer Fehler: In Schritt 2 noch einmal „auf“ eintragen. Die Schranke ist schon offen; dieselbe Eingabe t erzeugt im Zustand offen die Ausgabe T.

Ansatz: Arbeiten Sie Zeile für Zeile: Pfeil aus dem aktuellen Zustand mit der Eingabe dieser Zeile suchen.

Weiter: Das Ausgabewort sind die Ausgaben von oben nach unten; ε-Zeilen tragen nichts bei.

A6

Paritätsbit per Automat

AFB II Mix

Aus Kapitel 8 kennen Sie das Paritätsbit: Es wird so an ein Datenwort angehängt, dass die Anzahl der Einsen insgesamt gerade ist. Der folgende Mealy-Automat liest ein Datenwort Bit für Bit; g heißt „bisher gerade viele Einsen“, u „bisher ungerade viele“.

Paritätsbit-Erzeuger (Σ = Ω = {0, 1})

Bestimmen Sie Schritt für Schritt die Ausgaben und das Codewort (Bits ohne Leerzeichen eingeben).

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Ausgabewort zu 1011
Ausgabewort zu 1011001
Paritätsbit für 1011001
Gesendetes Codewort (Daten + Paritätsbit)

Jede Ausgabe ist das Paritätsbit für das bisher gelesene Anfangsstück; das letzte Ausgabezeichen ist das Paritätsbit des ganzen Datenworts. 1011001 enthält vier Einsen, also ist das Paritätsbit 0 und das Codewort 10110010. Typischer Fehler: das ganze Ausgabewort anhängen statt nur seines letzten Zeichens.

Ansatz: Starten Sie in g und folgen Sie den Pfeilen; notieren Sie hinter jedem Pfeil das Zeichen nach dem Schrägstrich.

Weiter: Das Paritätsbit ist das letzte Ausgabezeichen. Kontrolle: Einsen im Datenwort zählen.

A7

Der Fahrstuhl

AFB II

Ein Fahrstuhl mit zwei Etagen hat die Tasten h (hoch) und r (runter). Ausgabewörter werden hier durch Kommas getrennt notiert.

Fahrstuhl (Σ = {h, r})

Untersuchen Sie den Automaten und markieren Sie alle zutreffenden Aussagen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.

Dieselbe Taste h liefert im EG „fahre hoch“, im OG aber „Tür auf“ — die Ausgabe hängt von Zustand und Eingabe ab. Deshalb reicht der Zustand allein nicht. Die Längen stimmen hier überein, weil kein Pfeil ε ausgibt und jeder Pfeil genau ein Ausgabezeichen hat. Das ist eine Eigenschaft dieses Automaten, keine allgemeine Regel.

Ansatz: Spielen Sie jede genannte Eingabe am Graphen durch und schreiben Sie das Ausgabewort auf.

Weiter: rhrh beginnt im EG mit r — welcher Pfeil ist das?

A8

Protokoll eines Garagentors

AFB II

Ein Garagentor hat einen Knopf k und einen Endschalter e, der meldet, dass das Tor ganz offen bzw. ganz zu ist. Drückt man k, während das Tor schließt, fährt es zum Schutz wieder auf. Das Ablaufprotokoll (Zustand | Eingabe | Ausgabe | Folgezustand) für die Eingabe k e k k ab dem Startzustand zu ist durcheinandergeraten. Ordnen Sie die Zeilen in die richtige Reihenfolge ein.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1zu | k | Motor auf | öffnet

2öffnet | e | Motor aus | offen

3offen | k | Motor zu | schließt

4schließt | k | Motor auf | öffnet

5Ausgabewort: Motor auf, Motor aus, Motor zu, Motor auf

Zwei Regeln bestimmen die Reihenfolge: Die erste Zeile beginnt im Startzustand, und der Folgezustand einer Zeile ist der Zustand der nächsten. Wer nur auf die Eingabe achtet, verwechselt die beiden k-Zeilen „offen | k“ und „schließt | k“ leicht. Die Kette zu → öffnet → offen → schließt → öffnet legt sie eindeutig fest.

Ansatz: Welche Zeile beginnt im Startzustand zu?

Weiter: Folgezustand der einen Zeile = Zustand der nächsten. Das Ausgabewort fasst am Ende alles zusammen.

A9

Fehlersuche: Ampelprotokoll

AFB III

Eine Ampel wird im Takt t weitergeschaltet. Die Ausgaben sind Schaltbefehle für die Lampen; jeder Übergang gibt ein ganzes Ausgabewort aus. Übergangstabelle (Feld = Folgezustand / Ausgabe):

Übergangstabelle Ampel
Zustand	t
rot	rotgelb / gelb an
rotgelb	grün / rot aus, gelb aus, grün an
grün	gelb / grün aus, gelb an
gelb	rot / gelb aus, rot an

Lena hat das Ablaufprotokoll für t t t t t im Format „Zustand | Eingabe | Ausgabe | Folgezustand“ aufgeschrieben. Überprüfen Sie ihr Protokoll.

In diesem Protokoll stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.

Schritt 3 ist der tückische Fehler: „gelb an“ sieht plausibel aus, aber die Ausgabe gehört zum Übergang aus grün — dort muss Grün erst ausgeschaltet werden. Schritt 5 kopiert den Folgezustand aus Schritt 2, obwohl die Tabelle von rot nach rotgelb führt. Zeile 6 ist richtig — auch wenn sie Zeile 5 widerspricht.

Ansatz: Vergleichen Sie jede Zeile mit dem Tabellenfeld in der Zeile ihres Zustands — Ausgabe und Folgezustand.

Weiter: Prüfen Sie außerdem die Verkettung: Der Folgezustand von Schritt 4 muss der Zustand von Schritt 5 sein.

A10

Rückwärts gedacht

AFB III Trick

Der Treppenhausautomat aus A3 startet im Zustand aus und liest ein Eingabewort aus genau vier Zeichen T bzw. U. Er erzeugt dabei das Ausgabewort „an aus“. Ermitteln Sie, wie viele verschiedene Eingabewörter der Länge 4 genau dieses Ausgabewort erzeugen.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.

Die Falle: zu glauben, aus der Ausgabe lasse sich die Eingabe eindeutig zurückrechnen. Die ε-Schleifen („U / ε“ in aus, „T / ε“ in an) schlucken Zeichen ohne Spur. Nötig ist: erst U-Schleifen, ein T (an), dann T-Schleifen, ein U (aus), dann nur noch U-Schleifen. Das ergibt TTTU, TTUU, TUUU, UTTU, UTUU, UUTU — also 6 Wörter.

Ansatz: Welche Pfeile erzeugen „an“, welche „aus“, welche nichts?

Weiter: Das Wort besteht aus: U-Block (ε), T, T-Block (ε), U, U-Block (ε). Verteilen Sie die übrigen zwei Zeichen auf die drei Blöcke.

Übungen: Der Mealy-Automat

Übungsaufgaben