MINT üben

Grenzen endlicher Automaten

Dreißig Übungen zum Schubfachprinzip, zu aⁿbⁿ und zu Sprachen, die nur so aussehen, als müsste man zählen.

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
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.
A2
Ein Fenster aus vier Zeichen
AFB II

Ein Automat über \(\Sigma=\{0,\,1\}\) soll ein Wort annehmen, wenn unter seinen letzten vier Zeichen höchstens eine 1 steht (bei kürzeren Wörtern zählen alle Zeichen). Das Wort darf beliebig lang sein. Erklären Sie Schritt für Schritt, was der Automat sich merken muss, und ob die Sprache regulär ist.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Die Falle: Das Wort kann beliebig lang sein, doch das Gedächtnis des Automaten bleibt beschränkt. Maßgeblich ist nur, wie viele verschiedene Fenster-Inhalte es gibt — und das sind endlich viele.
    Fragen Sie bei jedem Schritt: Wie viele verschiedene Dinge muss der Automat unterscheiden — endlich viele oder unendlich viele?
    Die Länge des Wortes ist nicht das, was der Automat sich merkt. Er behält nur ein Fenster fester Größe.
    A3
    Mit DEA erkennbar?
    AFB I

    Ordnen Sie jede Sprache zu: Gibt es einen DEA, der sie erkennt?

    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).
    1mit DEA erkennbar
    2nicht mit DEA erkennbar
    Entscheidend ist, ob unbeschränkt gezählt oder gespeichert werden muss. aⁿbᵐ sieht aus wie aⁿbⁿ, verlangt aber keine gleiche Anzahl — ein DEA merkt sich nur, ob schon ein b kam. „Durch 4 teilbar“ braucht nur die Reste 0 bis 3; {aⁿbⁿ | n ≤ 4} ist endlich. Typischer Fehler: jede Sprache mit „Anzahl“ im Namen für nicht erkennbar halten.
    Ansatz: Fragen Sie bei jeder Sprache: Muss sich der Automat eine Zahl ohne obere Grenze merken?
    Weiter: Endliche Sprachen und Zählen „modulo“ oder „bis zu einer festen Grenze“ schafft ein DEA.