Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Deuten, Testen, Vermuten und Widerlegen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Was weiß der Automat?
AFB IBeim Analysieren beschreibt man zuerst, was der Automat in jedem Zustand über das bisher gelesene Wort „weiß“. Ordnen Sie jedem Zustand von Automat A seine Bedeutung zu.
Automat A, Σ = {a, b}
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Der erste Schritt entscheidet endgültig, in welcher „Hälfte“ der Automat bleibt: Von z1/z2 führt kein Pfeil zu z3/z4. Innerhalb einer Hälfte merkt er sich nur das zuletzt gelesene Zeichen. Typischer Fehler: z2 als „zuletzt b“ deuten und vergessen, dass der Automat sich auch den Anfang merkt — sonst wären z2 und z3 dieselbe Bedeutung.
Ansatz: Welche Wörter führen in den jeweiligen Zustand? Schreiben Sie zu jedem Zustand zwei kurze Beispiele auf.
Weiter: Die obere Reihe erreicht man nur mit einem a am Anfang, die untere nur mit einem b. Schleifen zeigen, welches Zeichen zuletzt kam.
A2
Durchgelassen oder nicht?
AFB IWenden Sie Automat A aus A1 auf jedes Wort an und sortieren Sie es ein.
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).
1akzeptiert
2abgelehnt
Akzeptiert werden genau die nichtleeren Wörter, deren erstes und letztes Zeichen übereinstimmen. Das einzelne
a gehört dazu — erstes und letztes Zeichen sind hier dasselbe. Typischer Fehler: ε einsortieren wie a. Nach dem leeren Wort steht der Automat in z0, und z0 ist kein Endzustand.Ansatz: Nur z1 und z3 sind Endzustände. Welches Zeichen muss am Anfang und am Ende stehen, um dort zu landen?
Weiter: Prüfen Sie die Grenzfälle einzeln: das leere Wort und Wörter der Länge 1.
A3
Automat B deuten
AFB IAutomat B ist als Übergangstabelle gegeben (→ Startzustand, doppelt unterstrichen: Endzustand). Nennen Sie jeweils, ob die Aussage stimmt.
| Zustand | a | b |
|---|---|---|
| z0 | z1 | z0 |
| z1 | z2 | z1 |
| z2 | z0 | z2 |
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Die a-Spalte bildet einen Zyklus z0 → z1 → z2 → z0: Der Automat zählt modulo 3. Typischer Fehler: „genau ein a“ statt „Rest 1“. Ein Zyklus bedeutet immer, dass der Automat nur einen Rest und keine absolute Anzahl kennt.
Ansatz: Verfolgen Sie in der a-Spalte, wohin man nach 1, 2, 3, 4 … a kommt.
Weiter: Ein Zyklus der Länge 3 kann nicht zwischen 1 und 4 a unterscheiden.
A4
Testwörter mit System
AFB ITestwörter prüft man systematisch: zuerst nach Länge, bei gleicher Länge alphabetisch (a vor b). Geben Sie die Reihenfolge an, in der die Wörter getestet werden.
Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1ε (leeres Wort)
2
a
3
b
4
aa
5
ab
6
bb
7
aab
8
abb
Richtig: ε,
a, b, aa, ab, bb, aab, abb. So vergisst man kein kurzes Wort — gerade dort verstecken sich Grenzfälle. Typischer Fehler: rein alphabetisch sortieren wie im Wörterbuch; dann stünde aab vor b, und ε ginge leicht ganz verloren.Ansatz: Zuerst das kürzeste Wort — welches Wort hat die Länge 0?
Weiter: Innerhalb einer Länge vergleicht man Zeichen für Zeichen von links, a kommt vor b.
A5
Testen, dann vermuten
AFB IIUntersuchen Sie Automat C mit den Testwörtern: In welchem Zustand steht er jeweils am Ende? Wählen Sie dann die Beschreibung, die zu allen Tests passt.
Automat C, Σ = {0, 1}
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
Nach 11:
Nach 101:
Nach 111:
Nach 1001:
Nach 1100:
Vermutung: Automat C akzeptiert .
11 (3) → z0, 101 (5) → z2, 111 (7) → z1, 1001 (9) → z0, 1100 (12) → z0. Jeder Zustand steht für einen Rest bei Division durch 3. Die Ablenker scheitern an einzelnen Tests: 101 hat zwei Einsen, wird aber abgelehnt; 111 hat drei Einsen, wird aber abgelehnt; 1001 endet auf 01 und wird akzeptiert. Typischer Fehler: nach zwei passenden Tests aufhören. Eine Vermutung gilt erst, wenn sie alle Testwörter erklärt.Ansatz: Arbeiten Sie jedes Wort mit dem Finger im Graphen ab. Notieren Sie daneben den Dezimalwert der Binärzahl.
Weiter: Vergleichen Sie Endzustand und Dezimalwert: 3, 9, 12 enden in z0 — was haben diese Zahlen gemeinsam?
A6
Automat D durchspielen
AFB IIBestimmen Sie für jedes Testwort den Zustand nach dem letzten Zeichen und ob Automat D es akzeptiert.
Automat D, Σ = {0, 1}
Tragen Sie den Zustand (z. B.
z1) und „ja“ oder „nein“ ein. Enter in einem Feld prüft ebenfalls.| Wort | Zustand am Ende | akzeptiert? (ja/nein) |
|---|---|---|
| ε | ||
101 | ||
0110 | ||
1100 | ||
0011 |
ε → z0 (nein),
101 → z1 (nein), 0110 → z2 (ja), 1100 → z0 (nein), 0011 → z3 (ja). Die Endzustände z2 und z3 erreicht man genau dann, wenn das vorletzte Zeichen eine 1 war. Typischer Fehler: bei 101 „ja“ tippen, weil das Wort mit 1 endet — entscheidend ist aber die vorletzte Stelle.Ansatz: Beginnen Sie jedes Wort in z0. Das leere Wort liest kein Zeichen.
Weiter: Von z1 führt 0 schräg nach unten links, von z2 führt 1 schräg nach oben rechts.
A7
Fehlersuche: Jonas’ Analyse
AFB IIJonas hat Automat D aus A6 analysiert. Überprüfen Sie seine Analyse — zwei Zeilen sind falsch.
In diesem Text stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Die Bedeutungen der Endzustände liefern die Bedingung — hier haben z2 und z3 gemeinsam, dass das vorletzte Zeichen 1 war. Daraus folgt die Mengenschreibweise in der letzten Zeile. Typischer Fehler: aus den Bedeutungen eine zu grobe Regel ableiten und keine Gegenprobe mit einem Wort wie
001 machen.Ansatz: Prüfen Sie jede Behauptung mit einem eigenen kurzen Testwort am Graphen aus A6.
Weiter: Suchen Sie ein Wort mit einer 1, das trotzdem abgelehnt wird. Und: In welchem Zustand endet das Wort 1?
A8
Wie viele Wörter der Länge 6?
AFB II TrickErmitteln Sie, wie viele der 64 Wörter der Länge 6 über \(\{a,\,b\}\) von Automat E akzeptiert werden.
Automat E, Σ = {a, b}
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Kein einziges: Der Pfeil zwischen z1 und z3 zeigt von z3 weg. In z3 führt nur die eigene Schleife — vom Startzustand aus ist der Endzustand unerreichbar, also \(L(E)=\emptyset\). Typischer Fehler: anfangen zu zählen, statt zuerst zu prüfen, welche Zustände vom Start aus überhaupt erreichbar sind.
Ansatz: Bevor Sie zählen: Welche Zustände erreicht der Automat vom Startzustand aus überhaupt?
Weiter: Achten Sie auf die Pfeilrichtung zwischen z1 und z3.
A9
Automat C und das Zweiersystem
AFB III MixAutomat C aus A5 liest Binärzahlen (Kapitel Codierung). Analysieren Sie, wie er das Wort 100111 verarbeitet.
Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
-
Dezimalwert von
100111 - Rest dieses Werts bei Division durch 3
-
Nach dem Präfix
1001steht der Automat in zi. Wie lautet i? -
Wie oft steht der Automat beim Lesen von
100111in z0 (Start mitgezählt)? - Nächstgrößere Zahl, die der Automat akzeptiert (dezimal)
\(100111_2=32+4+2+1=39\), und \(39=13\cdot 3\). Zustandsfolge: z0 → z1 → z2 → z1 → z0 → z1 → z0. Nach
1001 (= 9) steht der Automat in z0 — jeder Präfix endet im Zustand „Rest seines Werts“. Die nächste durch 3 teilbare Zahl ist 42 = 101010. Typischer Fehler: die Zustände von hinten lesen oder die Stellenwerte von rechts mit 1, 2, 4 … vergessen.Ansatz: Stellenwerte von rechts: 1, 2, 4, 8, 16, 32. Jeder Zustand zi bedeutet: Der bisher gelesene Präfix hat den Rest i bei Division durch 3.
Weiter: Hängt man an eine Binärzahl mit Wert x ein Zeichen c an, entsteht 2x + c. Daher führt z1 mit 0 nach z2.
A10
Die Sprache von Automat A
AFB IIIZurück zu Automat A aus A1. Beurteilen Sie die Beschreibungen seiner Sprache und markieren Sie alle, die zutreffen.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Die erste Zeile ist die vollständige Mengenschreibweise — ohne „w ≠ ε“ wäre sie für das leere Wort unklar. Die Palindrome passen nicht:
aaba liegt in L(A), ist aber kein Palindrom. aba beginnt mit ab und wird akzeptiert. Typischer Fehler: nur die obere Hälfte des Graphen deuten und die Wörter übersehen, die mit b beginnen und enden.Ansatz: Prüfen Sie jede Beschreibung mit einem Gegenbeispiel: ein Wort, das in L(A) liegt, aber nicht beschrieben wird — oder umgekehrt.
Weiter: Testen Sie
b, aba und aaba.