Dreißig Übungen zu e / a, ε und Ausgabewörtern — vom Ablesen am Graphen bis zum Rückwärtsdenken.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Klicken, Zuordnen, Nachverfolgen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
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
Die Schranke in Java
AFB IIMix
Eine Bahnschranke wird als Mealy-Automat in Java umgesetzt: Zustand 0 = offen, 1 = zu; Spalte 0 = a (Zug naht), 1 = v (Zug vorbei). Die Ausgaben sind die Texte senken und heben, die leere Ausgabe ε ist der leere String:
int[][] D = {{1, 0}, {1, 0}}; String[][] A = {{"senken", ""}, {"", "heben"}};
Ein Schüler hat die Methode verarbeite(String wort) geschrieben; z ist der Zustand, s die Spalte des gelesenen Zeichens, aus das Ausgabewort. Erklären Sie, welche Zeilen falsch sind: Klicken Sie sie an und tragen Sie die Korrektur ein.
Klicken Sie die Zeilen an, die Sie für falsch halten – dabei klappt ein Feld für die Korrektur auf. Geprüft wird beides: die Auswahl und die Korrekturen.
Richtig ist der Zugriff
Zurückgegeben wird
In A[i][j] ist i der Zustand (Zeile) und j die Spalte des Zeichens, also A[z][s]. Die Ausgabe wird vor dem Zustandswechsel angehängt, der Wechsel steht in der Zeile danach richtig. Zurückgegeben wird das Ausgabewort aus, nicht der Zustand z.
Die Ausgabe hängt vom Zustand ab, in dem der Automat vor dem Lesen steht. Überlegen Sie, in welcher Zeile z sich ändert.
Das Ausgabewort wächst bei jedem Schritt (+=). Die Methode soll das Ausgabewort liefern, nicht den Zustand.
A3
Schlussfolgerungen zu Mealy-Automaten
AFB II
Erläutern Sie jede Schlussfolgerung über Mealy-Automaten: Ist sie richtig gedacht, oder steckt ein Denkfehler darin? Wischen Sie die Karte auf den passenden Stapel.
Wischen Sie die oberste Karte nach links (richtig gedacht) oder nach rechts (Denkfehler) – mit Maus oder Finger ziehen oder die Knöpfe nutzen. Tastatur: Fokus auf die Karte, ←/→. Ein Klick auf eine abgelegte Karte holt sie zurück. Ist der Stapel leer, prüfen Sie.
Jedes gelesene Zeichen löst genau einen Übergang aus, auch einen mit ε, und ein ε-Übergang darf den Zustand wechseln. Ein leeres Ausgabewort sagt nichts über „Annehmen“: Den Begriff gibt es beim Mealy-Automaten nicht. Die Ausgabe hängt von Zustand und Zeichen ab, deshalb darf a in verschiedenen Zuständen Verschiedenes ausgeben. Gleiche Ausgabe bedeutet nicht gleichen Folgezustand. Weil der Automat deterministisch ist, bleibt das Ausgabewort zu einem Eingabewort gleich – umgekehrt führen ε-Schleifen dazu, dass verschiedene Eingaben dieselbe Ausgabe erzeugen.
Fragen Sie sich bei jeder Karte: Hängt die Aussage nur vom Zustand ab, nur vom Zeichen, oder von beidem? Prüfen Sie Sonderfälle wie ε.
Beim Mealy-Automaten entscheiden Zustand und Zeichen gemeinsam über Folgezustand und Ausgabe – aber beide Größen sind unabhängig voneinander.
