Übungsaufgaben
Zehn Übungen zum Ablesen, Verfolgen, Übersetzen und Zählen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
Nennen Sie alle Aussagen, die für jeden deterministischen endlichen Automaten gelten.
Ordnen Sie jedes Wort zu: Nimmt der Automat es an oder lehnt er es ab?
Nicht eingezeichnete Übergänge führen in einen Fehlerzustand zF.
0815 wird angenommen — der Automat verbietet führende Nullen nicht. − allein endet in z1, ε bleibt in z0: beides keine Endzustände. 4−2 und +−3 laufen in den nicht gezeichneten Fehlerzustand. Typischer Fehler: nach dem eigenen Zahlgefühl entscheiden statt nach dem Graphen.Der Automat über \(\Sigma=\{0,\,1\}\) ist als Übergangstabelle gegeben (→ Startzustand, doppelt unterstrichen: Endzustand). Lesen Sie der Tabelle ab, ob die Aussagen stimmen.
| Zustand | 0 | 1 |
|---|---|---|
| z0 | z0 | z1 |
| z1 | z1 | z2 |
| z2 | z2 | z2 |
Geben Sie die Zustandsfolge an, die der Automat beim Lesen von abbaba durchläuft, und entscheiden Sie über das Wort.
Wort: abbaba
Nach Zeichen 1 (a):
Nach Zeichen 2 (b):
Nach Zeichen 3 (b):
Nach Zeichen 4 (a):
Nach Zeichen 5 (b):
Nach Zeichen 6 (a):
Ergebnis: Das Wort wird .
abb in z1 bleiben oder in z2 verharren. Der b-Pfeil aus z2 führt zurück nach z0 — das angefangene Muster ist zerstört.Erstellen Sie die vollständige Übergangstabelle zum Graphen — einschließlich des Fehlerzustands.
Nicht eingezeichnete Übergänge führen in einen Fehlerzustand zF.
z2 oder zF). Enter in einem Feld prüft ebenfalls.| Zustand | 0 | 1 |
|---|---|---|
| z0 | ||
| z1 | ||
| z2 | ||
| zF |
0 darf nichts mehr kommen, also δ(z1, 0) = δ(z1, 1) = zF. Der Fehlerzustand selbst braucht ebenfalls eine vollständige Zeile — er führt immer in sich selbst. Typischer Fehler: die zF-Zeile weglassen oder die Felder von z1 leer lassen. Eine vollständige Tabelle hat |Z| · |Σ| = 4 · 2 = 8 Einträge.Bestimmen Sie für jedes Wort den Zustand nach dem letzten Zeichen und verbinden Sie beide.
001100 → z0, 01010 → z1, 10110 → z2, 0111 → z3 (nur dieses Wort wird akzeptiert). Abkürzung: Jede 0 wechselt zwischen linker und rechter Spalte, jede 1 zwischen oberer und unterer Zeile. Es zählt also nur, ob die Anzahl der Nullen und der Einsen gerade oder ungerade ist. Typischer Fehler: sich bei den langen Wörtern verzählen, weil man zwei Zeichen auf einmal verarbeitet.Max prüft, ob der Graph einen DEA darstellt. Überprüfen Sie seine Notizen — drei Zeilen sind falsch.
Verbinden Sie den DEA mit dem Kapitel Algorithmen. Erläutern Sie, wie ein Automat ein Wort abarbeitet, indem Sie die Lücken füllen. Drei Begriffe bleiben übrig.
Ein DEA lässt sich direkt als Algorithmus ausführen: Eine liest das Wort Zeichen für Zeichen. In jedem Durchlauf bestimmt eine aus aktuellem Zustand und Zeichen den Folgezustand. Bei einem Wort der Länge n gibt es genau n Durchläufe — die Laufzeit wächst mit der Wortlänge. Als Speicher genügt eine einzige für den aktuellen Zustand, egal wie lang das Wort ist. Zurückgegeben wird am Ende ein : wahr genau dann, wenn der letzte Zustand ein Endzustand ist.
switch) — jedes Zeichen wird genau einmal angefasst: lineare Laufzeit. Der Speicherbedarf bleibt konstant, denn der Automat merkt sich nur seinen Zustand, nie die gelesenen Zeichen. Genau das bedeutet „endlich“. Typischer Fehler: eine Reihung aller gelesenen Zeichen anlegen. Die braucht ein DEA nie.Der Graph aus A2 zeigt nur sechs Pfeilbeschriftungen. Berechnen Sie, wie viele Übergänge der vollständige DEA zu \(\Sigma=\{+,\,-,\,0,\,1,\,\dots,\,9\}\) hat — mit Fehlerzustand.
Analysieren Sie die Sprache \(L(A)\) des Automaten aus A4, indem Sie Wörter systematisch zählen.
- Anzahl aller Wörter der Länge 4 über Σ = {a, b}
- Davon akzeptiert
- Akzeptierte Wörter der Länge 5
-
Länge des kürzesten akzeptierten Worts, das mit
bbbeginnt
aba enthalten. Länge 4: abaa, abab, aaba, baba. Länge 5: 11 von 32 Wörtern. Das kürzeste mit bb beginnende ist bbaba. Typischer Fehler: Wörter mit aba doppelt zählen, wenn das Muster zweimal vorkommt (z. B. ababa) — jedes Wort zählt nur einmal.