Grenzen endlicher Automaten: Übungen – Informatik Grundkurs

Ihr Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.

Zustände im Parkhaus

AFB I

Die Schranke eines Parkhauses mit 35 Plätzen wird als DEA modelliert. Der Zustand merkt sich die Zahl der belegten Plätze (0 bis 35); die Eingabe e steht für eine Einfahrt, a für eine Ausfahrt. Eine Einfahrt in das volle und eine Ausfahrt aus dem leeren Haus führen in den Fehlerzustand zF, aus dem es kein Zurück gibt. Berechnen Sie, wie viele Zustände der Automat insgesamt hat.

Schieben Sie den Regler auf Ihr Ergebnis — Pfeiltasten bewegen ihn feiner. Nach dem Prüfen sehen Sie den Trefferbereich.

0 Zustände60 Zustände

Jede Zahl belegter Plätze von 0 bis 35 ist ein eigener Zustand: Das sind 36 Zustände, nicht 35. Dazu kommt der Fehlerzustand zF, also 37. Beschränktes Zählen ist für einen DEA möglich, es kostet aber einen Zustand pro Zählerstand.

Jede Zahl belegter Plätze, die der Automat unterscheiden muss, ist ein eigener Zustand — auch die Zahl 0.

Von 0 bis 35 sind es 36 verschiedene Zahlen. Vergessen Sie den Fehlerzustand zF nicht, er ist ein Zustand wie jeder andere.

Wie gut passt ein DEA?

AFB II

Schätzen Sie ab, wie gut sich ein DEA für jede Aufgabe bauen lässt (1 = kein DEA möglich, 3 = nur mit sehr vielen Zuständen, 5 = mit ganz wenigen Zuständen). Eine Stufe Abweichung ist erlaubt.

Schätzen Sie für jede Aufgabe ein, wie gut sich ein DEA dafür bauen lässt. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.

1 = kein DEA möglich5 = ganz wenige Zustände

Ob ein Wort über {0, 1} mit einer 1 endet.

Ob die Länge eines Wortes aus lauter a durch 6 teilbar ist.

Ob ein Wort über {a, b} höchstens 100 Zeichen lang ist.

Ob ein Text genauso viele Vokale wie Konsonanten enthält.

Ob ein Wort aus zwei gleichen Hälften besteht, zum Beispiel abab.

Ein Wort endet auf 1 oder nicht: zwei Zustände genügen. Die Länge modulo 6 braucht sechs Zustände im Kreis. „Höchstens 100 Zeichen“ ist beschränktes Zählen: möglich, aber mit 102 Zuständen (0 bis 100 Zeichen und der Fehlerzustand) — Stufe 3. Gleich viele Vokale wie Konsonanten verlangt unbeschränktes Zählen, und bei zwei gleichen Hälften müsste sich der Automat die ganze erste Hälfte merken: Beides schafft kein DEA.

Fragen Sie bei jeder Aufgabe: Muss der Automat eine Zahl ohne obere Grenze oder ein beliebig langes Stück des Worts speichern?

Beschränktes Zählen und Zählen im Kreis (modulo) sind möglich — je größer die Grenze, desto mehr Zustände. Unmöglich wird es bei unbeschränktem Vergleichen.

Schubfach an einem Beispiel

AFB II

Ein DEA A mit 5 Zuständen soll L₌ = {w ∈ {a, b}* | w enthält gleich viele a wie b} erkennen. Wenden Sie die Beweisidee Schritt für Schritt auf diesen Fall an (Wörter ohne Leerzeichen, Antwort in Schritt 4: angenommen oder abgelehnt).

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

Anzahl der Vorgeschichten a⁰, a¹, …, a⁵
Mindestens so viele davon enden sicher im selben Zustand
Angenommen, a² und a⁵ enden im selben Zustand. Kürzester Anhang w mit a²w ∈ L₌
Wenn A das Wort a²bb richtig behandelt: Was macht A mit a⁵bb?

Sechs Vorgeschichten, fünf Zustände — zwei teilen sich sicher einen Zustand. Da a²bb ∈ L₌ angenommen wird, muss A auch a⁵bb annehmen, obwohl dort 5 a auf 2 b kommen. Typischer Fehler im letzten Schritt: „abgelehnt“ antworten, weil a⁵bb nicht zu L₌ gehört. Gefragt ist aber, was A tut — und genau darin liegt der Widerspruch.

Ansatz: k Zustände, k + 1 Vorgeschichten: Das Schubfachprinzip erzwingt eine Wiederholung.

Weiter: Gleicher Zustand ⇒ gleiche Entscheidung für jede gleiche Fortsetzung — unabhängig davon, was richtig wäre.