Lernziele
In dieser Aufgabe …
- festigen die Studierenden ihre Kenntnisse über endliche Automaten.
- üben die Studierenden die interpretation von Zustandsübergangsdiagrammen von Schaltungen.
Endlicher Automat 2
Gegeben ist das Zustandsübergangsdiagramm für einen endlichen Automaten:
Diese Aufgabe war Teil der Klausur im Sommersemester 2024 (Ersttermin).
a)
Level 3: Anwenden
Welche beiden Eingabefolgen an den Automaten können zur Ausgabe 0001 nach dem Reset des Automaten führen?
Lösung
Eingabefolge 1: /A, /A, A, B
A: 001x
B: xxx1Eingabefolge 2: A, /B, A, B
A: 1x1x
B: x0x1Notationshinweis: 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.
b)
Level 3: Anwenden
Kann der Automat die Ausgabe 0011 erzeugen? Begründen Sie Ihre Antwort.
Lösung
Nein, da die Ausgabe 1 nur im Zustand S2 erfolgt. Um dorthin zu gelangen, braucht es immer eine ungerade Anzahl an Zuständen mit Ausgabe 0 (siehe erste Teilaufgabe). Außerdem gibt es keinen Übergang von S2 zu S2, um direkt nacheinander zweimal die Ausgabe 1 zu erzeugen.
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 Moore-Automaten, da die Ausgabe mit dem Zustand verknüpft ist, nicht mit den Übergängen dazwischen.