Automaten im Abitur: Übungen – Informatik Grundkurs

A1

Was gehört zu einem DEA?

AFB I

Gib alle Bestandteile an, die zur vollständigen Beschreibung eines DEA gehören.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Prüfen“.

Ausgaben hat der Mealy-Automat, einen Keller der Kellerautomat — beide gehören nicht zum DEA.

Frage: Was braucht der Automat, um ein Wort zu lesen und zu entscheiden?Warum? Alphabet, Zustände, Start, Ende, Übergänge.

Hilfe: Ω gehört zum Mealy-Automaten.

A2

Stimmt's? — Akzeptieren

AFB I

DEA über Σ = {0, 1}, Start z0, Endzustand z0
Zustand	0	1
z0	z0	z1
z1	z1	z0

Fünf Aussagen zu diesem DEA. Ordne sie als richtig oder falsch ein.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Jeder Zustand speichert eine Eigenschaft des bisher gelesenen Wortes — hier „gerade“ oder „ungerade“ viele Einsen.

Frage: Was ändert eine 1, was eine 0?Warum? Nur die Einsen wechseln den Zustand.

Hilfe: Endzustand z0 steht für „gerade“.

A3

Mealy-Automat

AFB I

Beschreibe einen Mealy-Automaten, indem du die Lücken füllst — ein Wort bleibt übrig.

Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.

Bei einem Mealy-Automaten erzeugt jeder eine . Die möglichen Ausgabezeichen bilden das Ω. Eine leere Ausgabe notiert man mit . Anders als beim DEA braucht er keine .

Der Keller gehört zum Kellerautomaten (nur erhöhtes Anforderungsniveau).

Frage: Wo steht beim Mealy-Automaten die Ausgabe?Warum? Am Übergang: Eingabe / Ausgabe.

Hilfe: Ein Mealy-Automat übersetzt, er entscheidet nicht.

A4

DEA möglich?

AFB I

Ordne jede Sprache über Σ = {a, b} zu: Gibt es einen DEA dafür?

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

1DEA möglich

2kein DEA möglich

Ein DEA hat nur endlich viele Zustände und kann deshalb nicht beliebig weit zählen. „Höchstens drei a“ geht, weil man nur bis vier zählen muss.

Frage: Muss der Automat eine unbeschränkt große Zahl speichern?Warum? Endlich viele Zustände = endliches Gedächtnis.

Hilfe: Bis 3 zählen geht, beliebig weit nicht.

A5

Zustand nach der Eingabe

AFB I

DEA über Σ = {0, 1}, Start z0, Endzustand z0
Zustand	0	1
z0	z0	z1
z1	z1	z0

Wende den DEA auf das Wort 1101101 an. Gib die Anzahl der Übergänge an, bei denen der Zustand wechselt.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.

Jede 1 wechselt den Zustand, jede 0 nicht: fünf Einsen, fünf Wechsel. Endzustand z1 — das Wort wird abgelehnt.

Frage: Welches Zeichen führt zu einem Wechsel?Warum? Nur 1.

Hilfe: Zähle die Einsen.

A6

Einen DEA entwerfen

AFB II

Gesucht ist ein DEA über {0, 1}, der Wörter akzeptiert, die mit 00 enden. Stelle ein sinnvolles Vorgehen in der richtigen Reihenfolge dar.

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

1Beispielwörter sammeln: 100 ja, 010 nein

2Bedeutung der Zustände festlegen: „kein Ende 0“, „endet auf 0“, „endet auf 00“

3Startzustand und Endzustand bestimmen

4Für jeden Zustand beide Übergänge eintragen

5Mit den Beispielwörtern testen

Zustände mit Bedeutung sind der Schlüssel. Der Zustand „endet auf 00“ bleibt bei einer weiteren 0 erhalten.

Frage: Was muss der Automat sich über das Ende des Wortes merken?Warum? Höchstens die letzten zwei Zeichen.

Hilfe: Erst Bedeutungen, dann Pfeile, dann testen.

A7

Getränkeautomat als Mealy-Automat

AFB II

Ein Automat nimmt 50-Cent-Münzen (m) und gibt nach zwei Münzen eine Flasche aus: z0 —m / ε→ z1, z1 —m / Flasche→ z0; die Taste r bewirkt z0 —r / ε→ z0 und z1 —r / 50ct→ z0. Ermittle für die Eingabe m m m r m die Werte.

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

Anzahl ausgegebener Flaschen:
Anzahl zurückgegebener 50-ct-Münzen:
Nummer des Endzustands (z…):

z0 m→z1; m→z0 (Flasche); m→z1; r→z0 (50 ct zurück); m→z1. Ende in z1.

Frage: Was gibt der Übergang von z1 mit m aus?Warum? Die zweite Münze bringt die Flasche.

Hilfe: r in z1 gibt die eingeworfene Münze zurück.

A8

Vom Graphen zum Code

AFB II

Erläutere die Implementierung eines Automaten, indem du jedes Element mit seiner Umsetzung verbindest.

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

Wird der Fehlerzustand erreicht, kann die Operation sofort falsch zurückgeben — er wird nie wieder verlassen.

Frage: Wodurch wird das „Gedächtnis“ des Automaten im Code dargestellt?Warum? Durch genau eine Variable.

Hilfe: Für jedes Zeichen eine Entscheidung — also Schleife mit Verzweigung.

A9

Nils prüft seinen DEA

AFB II

Nils soll einen DEA für „Wörter über {a, b} mit genau einem b“ zeichnen: z0 (Start), z1 (Endzustand), z2. Überprüfe seine Übergänge.

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.

Nach den Vorgaben darf der Fehlerzustand nur weggelassen werden, wenn das erläutert wird — ein vorhandener Zustand ohne Pfeile ist unvollständig.

Frage: Was soll nach dem ersten b bei weiteren a passieren?Warum? Die Zahl der b bleibt 1.

Hilfe: Jeder Zustand braucht Pfeile für a und b.

A10

Wie viele Zustände?

AFB III

Beurteile, wie viele Zustände ein möglichst kleiner vollständiger DEA über {a, b} braucht (Fehlerzustand mitgezählt).

Wähle für jede Zeile eine Stufe: 1 = 1, 2 = 2, 3 = 3, 4 = 4, 5 = 5. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.

1 = 15 = 5

alle Wörter

Wörter mit gerader Länge

Wörter, die auf ab enden

Wörter, die mit ab beginnen

Wörter mit genau drei a

Beginnt mit ab: Start, „a gelesen“, „ab gelesen“ und Fehlerzustand. Genau drei a: 0, 1, 2, 3 a gelesen und „zu viele“.

Frage: Was muss sich der Automat jeweils merken?Warum? Jede verschiedene Information braucht einen Zustand.

Hilfe: Fehlerzustand nicht vergessen.

Übungen: Automaten im Abitur

Übungsaufgaben