Aufgabenblock — AFB I
Zehn Standardaufgaben zum Reproduzieren: Graphen und Tabellen lesen, Wörter prüfen, Ausgaben bestimmen. Das sind die sicheren Punkte in jeder Klausur zu endlichen Automaten — bei jeder Aufgabe gibt es eine Erinnerung und die Lösung zum Aufklappen.
Ein vollständiger DEA hat die Zustände z0, z1, z2, z3 und den Fehlerzustand zF sowie das Eingabealphabet \(\Sigma=\{0,\,1,\,2\}\). Berechnen Sie, wie viele Übergänge (Pfeile einschließlich Schleifen) sein Zustandsgraph besitzt.
Lösung anzeigen
\(|Z|\cdot|\Sigma| = 5\cdot 3\) = 15 Übergänge
Davon sind die drei Schleifen an zF enthalten; ohne Fehlerzustand (mit Vermerk) würden alle Pfeile nach zF und von zF fehlen.
Ein Fahrstuhl in einem Haus mit drei Etagen wird durch den folgenden Zustandsgraphen modelliert: E0, E1, E2 sind die Etagen, h steht für die Taste „hoch“, r für „runter“.
Entnehmen Sie dem Graphen, in welcher Etage der Fahrstuhl nach der Eingabefolge h h r h h h steht.
Lösung anzeigen
E0 \(\xrightarrow{\text{h}}\) E1 \(\xrightarrow{\text{h}}\) E2 \(\xrightarrow{\text{r}}\) E1 \(\xrightarrow{\text{h}}\) E2 \(\xrightarrow{\text{h}}\) E2 \(\xrightarrow{\text{h}}\) E2 → Etage 2
Die letzten beiden h sind Schleifen: In E2 ändert „hoch“ nichts mehr.
Der DEA prüft ganze Zahlen mit optionalem Vorzeichen, \(\Sigma=\{+,\,-,\,0,\,1,\,\dots,\,9\}\). Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.
Wenden Sie den Automaten auf die folgenden Wörter an. Wie viele davon akzeptiert er?
−712+3−4+05−+1
Lösung anzeigen
| Wort | Zustandsfolge | Ergebnis |
|---|---|---|
−7 | z0 · z1 · z2 | akzeptiert |
12 | z0 · z2 · z2 | akzeptiert |
+ | z0 · z1 | abgelehnt |
3−4 | z0 · z2 · zF · zF | abgelehnt |
+05 | z0 · z1 · z2 · z2 | akzeptiert |
−+1 | z0 · z1 · zF · zF | abgelehnt |
→ 3 Wörter (−7, 12, +05). + endet in z1, das kein Endzustand ist.