Lernziele
In dieser Aufgabe …
- festigen die Studierenden ihre Kenntnisse über endliche Automaten.
- üben die Studierenden die Interpretation von Zustandsübergangsdiagrammen.
Endlicher Automat 1
Gegeben ist das Zustandsübergangsdiagramm für einen endlichen Automaten:
Diese Aufgabe war Teil der Klausur im Sommersemester 2024 (Zweittermin).
a)
Level 3: Anwenden
Welche Eingabewerte A und B müssen am Automaten anliegen, damit eine 1 ausgegeben wird?
Lösung
Nur am Übergang S2→S2 ist der Ausgabewert eine 1. Die Transition trägt das Label AB/1, womit A*B gelten muss. Somit ist klar: A=B=1.
b)
Level 3: Anwenden
Kann der Automat die Ausgabe 00001 erzeugen? Begründen Sie Ihre Antwort.
Lösung
Ja, z. B. mit den Eingabefolgen:
A, /B, A, B, (A*B)oder
/A, /A, A, B, (A*B)Notationshinweis: Wenn an einer Transition nur ein Literal steht, kann die andere Eingabe einen beliebigen Wert annehmen. Wir sprechen von “any” bzw. “don’t care”. Die Eingabe A steht also für (A = 1, B = x) mit x = any.
c)
Level 1: Wissen
Ist der im Zustandsübergangsdiagramm abgebildete Automat ein Moore- oder ein Mealy-Automat? Begründen Sie Ihre Antwort!
Lösung
Es handelt sich um einen Mealy-Automaten, da die Ausgabe beim Zustandsübergang geschieht.