Ü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.
Jede Java-Zeile einer Automaten-Klasse setzt einen Teil des Modells um. Ordnen Sie jedem Code-Baustein seine Aufgabe im Automaten zu.
zustand = 0; für „den Fehlerzustand setzen“ zu halten. Die Zahl 0 steht hier für z0, also den Startzustand — welcher Zustand welche Nummer hat, legt nur der Kommentar am Attribut fest. Ebenso ist return -1; kein Zustand, sondern ein Signal an akzeptiert, dass das Zeichen nicht zu Σ gehört.return: Eine davon steht in spalte, die andere am Ende von akzeptiert.delta ist die Übergangstabelle: Zeile = Zustand, Spalte = Zeichen, Eintrag = Folgezustand.Ein DEA über Σ = {0, 1} akzeptiert genau die Binärzahlen, die durch 3 teilbar sind. Zustand zr bedeutet: Die bisher gelesene Zahl lässt beim Teilen durch 3 den Rest r. Zeichen außerhalb von Σ führen in den nicht eingetragenen Fehlerzustand zF.
| Zustand | 0 | 1 |
|---|---|---|
| z0 | z0 | z1 |
| z1 | z2 | z0 |
| z2 | z1 | z2 |
Geben Sie für jede Lücke der Java-Klasse den passenden Eintrag an.
public class DurchDrei { private int zustand; // 0 = z0, 1 = z1, 2 = z2, 3 = zF public void uebergang(char c) { switch (zustand) { case 0: if (c == '0') { zustand = 0; } else if (c == '1') { zustand = ; } else { zustand = 3; } break; case 1: if (c == '0') { zustand = ; } else if (c == '1') { zustand = ; } else { zustand = 3; } break; case 2: if (c == '0') { zustand = ; } else if (c == '1') { zustand = 2; } else { zustand = 3; } break; default: zustand = ; } } public boolean akzeptiert(String wort) { zustand = 0; for (int i = 0; i < wort.length(); i++) { uebergang(wort.charAt(i)); } return ; } }
zustand != 3: Sie akzeptiert jede gültige Binärzahl, nicht nur die durch 3 teilbaren. Endzustand ist allein z0 (Rest 0) — deshalb wird auch das leere Wort akzeptiert. Im default-Zweig bleibt zF zF: kein Weg zurück.case, Spalte = das Zeichen im if.Ein DEA über {0, 1} erlaubt keine zwei Einsen hintereinander: z0 (Start, letztes Zeichen keine 1) und z1 (letztes Zeichen eine 1) sind Endzustände, eine zweite 1 in Folge führt aus z1 nach zF = 2, ebenso jedes Zeichen außerhalb von {0, 1}. Die Methode akzeptiert bricht ab, sobald der Fehlerzustand erreicht ist:
zustand = 0; int n = wort.length(); for (int i = 0; i < n; i++) { uebergang(wort.charAt(i)); if (zustand == 2) { return false; } } return true;
Eine Kollegin behauptet, die Wörter 110101, 1010100 und 0x01 lösten zusammen genau 11 Aufrufe von uebergang aus. Bestätigen Sie die Zahl, indem Sie für jedes Wort einzeln zählen.