Einen DEA entwickeln: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Übungen zum Planen, Ausfüllen, Reparieren und Entwerfen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

Der Weg zum Automaten

AFB I

Sara soll einen DEA für Variablennamen entwickeln. Stellen Sie ihr Vorgehen in der richtigen Reihenfolge dar.

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

1Eingabealphabet Σ festlegen

2Überlegen, was sich der Automat merken muss — jede mögliche Antwort wird ein Zustand mit Bedeutung

3Startzustand und Endzustände festlegen

4Für jeden Zustand und jedes Zeichen den Folgezustand bestimmen, bei Bedarf mit Fehlerzustand

5Mit Testwörtern und Grenzfällen prüfen

Erst das Gedächtnis, dann die Pfeile: Welche Zustände es gibt, folgt aus der Frage, was sich der Automat merken muss. Start und Ende ergeben sich aus den Bedeutungen, die Übergänge zuletzt. Typischer Fehler: sofort Pfeile zeichnen. Dann entstehen Zustände ohne klare Bedeutung, und beim Testen weiß niemand, was repariert werden muss.

Ansatz: Ohne Alphabet weiß man nicht, welche Zeichen überhaupt vorkommen.

Weiter: Übergänge kann man erst eintragen, wenn die Zustände mit ihrer Bedeutung feststehen. Getestet wird am Schluss.

Probleme und Abhilfen

AFB II

Erläutern Sie, wie man beim Testen entdeckte Probleme eines DEA-Entwurfs behebt: Finden Sie zu jedem Problem die passende Abhilfe.

Decken Sie zwei Karten auf, die zusammengehören. Mit der Tastatur: Tab zur Karte, Enter aufdecken, Pfeiltasten zum Wandern.

Jedes Problem zeigt auf einen Entwurfsschritt: Endzustände legen fest, was angenommen wird; die Tabelle muss vollständig sein; Zustände mit gleicher Bedeutung sind überflüssig; das leere Wort hängt am Startzustand; ein Fehlerzustand fängt verlorene Wörter ab; und jeder Zustand braucht eine Bedeutung.

Fragen Sie bei jedem Problem, welcher Teil des Automaten dafür zuständig ist: Zustände, Endzustände, Startzustand oder Übergänge.

Das leere Wort ε wird nur angenommen, wenn der Startzustand zugleich Endzustand ist; und ein Fehlerzustand hat für jedes Zeichen eine Schleife.

Graph und Tabelle

AFB III

Ein DEA über \(\Sigma=\{a,\,b\}\) akzeptiert genau die Wörter, die mit aa beginnen. Links steht sein Zustandsgraph (die Zustände heißen dort P, Q und R; nicht eingezeichnete Übergänge führen in den Fehlerzustand), rechts die vollständige Übergangstabelle. Beurteilen Sie, welcher Zustand des Graphen zu welcher Zeile der Tabelle gehört. Nicht jedes Teil hat ein Gegenstück.

Klicken Sie ein Teil im einen Bild an und dann das Teil im anderen Bild, das denselben Zustand meint — das Paar bekommt eine gemeinsame Farbe und Nummer. Ein Klick auf ein gepaartes Teil löst das Paar. Tastatur: Tab zu den Teilen, Enter wählt, ←/→ wechselt das Bild. Nicht jedes Teil hat ein Gegenstück.

Zustandsgraph

Übergangstabelle

Q trägt den Startpfeil und gehört zur Zeile mit dem Pfeil (z0), P trägt den Doppelkreis und gehört zur doppelt unterstrichenen Zeile (z2). R liegt dazwischen: z1. Die Zeile zF hat im Graphen keinen Zustand, weil sie dort nur als Vermerk steht.

Suchen Sie zuerst den Startzustand und den Endzustand: Startpfeil und Doppelkreis finden Sie auch in der Tabelle wieder.

Der dritte Zustand liegt dazwischen: Er erreicht den Endzustand mit a. Eine Zeile der Tabelle gehört zu keinem Zustand des Graphen — sie ist der Fehlerzustand.