Übung AFB I

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.

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.

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?

• −7
• 12
• +
• 3−4
• +05
• −+1

Ein DEA über \(\Sigma=\{0,\,1\}\) ist durch seine Übergangstabelle gegeben (→ Startzustand, doppelt unterstrichen: Endzustand).

Bestimmen Sie die Zustandsfolge für das Wort 1101. Geben Sie die Nummer des Zustands an, in dem der Automat endet (z. B. 2 für z2).

Ein Fahrkartenautomat verkauft Fahrkarten zu 2 €. Er nimmt 1-€- und 2-€-Münzen an und gibt, falls nötig, 1 € zurück. Die Tabelle gibt je Feld Folgezustand / Ausgabe an, \(\varepsilon\) heißt „keine Ausgabe“.

Nennen Sie für die Eingabefolge 1 € · 2 € · 1 € · 1 € · 2 € die Anzahl der ausgegebenen Fahrkarten und das insgesamt zurückgegebene Geld.

Der folgende DEA prüft Dezimalzahlen wie 12,5 oder 0,25. Dabei steht die Spalte „Ziffer“ für jedes der Zeichen 0 bis 9.

Zeichnen Sie den Zustandsgraphen. Den Fehlerzustand dürfen Sie mit Vermerk weglassen. Wie viele Pfeile (Schleifen mitgezählt, ohne Startpfeil) enthält Ihr Graph dann?

Der Mealy-Automat liest Bits, \(\Sigma=\Omega=\{0,\,1\}\).

Ermitteln Sie das Ausgabewort zum Eingabewort 1101.

Ein Automat prüft Bezeichner (Variablennamen). Ein Programm speichert seine Übergänge als zweidimensionales Feld delta: Zeile = Zustandsnummer (z0 → 0, z1 → 1, zF → 2), Spalte = Zeichenklasse (Buchstabe → 0, Ziffer → 1, Unterstrich → 2). Start ist 0, Endzustand ist 1.

Stellen Sie die Verarbeitung des Worts 7up in einer Tracetabelle dar (Zeichen, Spalte, neuer Wert von zustand). Welchen Wert hat zustand am Ende?

Ein DEA mit 6 Zuständen liest nacheinander die Vorgeschichten ε, a, aa, aaa, … Geben Sie die kleinste Zahl \(n\) an, für die unter den Vorgeschichten \(a^0,\,a^1,\,\dots,\,a^n\) garantiert zwei im selben Zustand enden.

Das Treppenhauslicht wird durch einen Mealy-Automaten gesteuert: T ist der Tastendruck, t meldet „eine Minute vergangen“.

Ordnen Sie die Zeichen T, t, an, aus und \(\varepsilon\) dem Eingabealphabet \(\Sigma\) oder dem Ausgabealphabet \(\Omega\) zu. Wie viele Elemente hat \(\Omega\)?