3.3 Computersysteme I, Automatenmodelle für Schaltwerke

Frage	Antworten
Was ist ein "Automat"?	ein Modell für ein diskretes, zeitveränderliches System.
Wie können Automaten formal beschrieben werden?	Durch ein 6-Tupel aus: Eingabealphabet I, Startzustand \(s_0\), Menge der Zustände S, Übergangsfunktion g, Ausgangsfunktion f, Ausgabealphabet O
Wann spricht man von einem endlichen Automaten?	Wenn das Eingangsalphabet, die Menge der Zustände und das Ausgabealphabet endlich sind.
Was ist das Eingabe-/Ausgabealphabet?	die Menge der möglichen Eingabe-/Ausgabezeichen
Wie wird ein endlicher Automat noch genannt? (Englisch)	Finite State Machine (FSM)
Was macht die Übergangsfunktion in einem Automaten?	diese liefert für jedes Paar aus einem Zustand und einem Eingabezeichen einen eindeutig bestimmten Folgezustand g : S × I → S
Durch welche Funktion werden bei einem Automaten die Ausgabezeichen bestimmt?	Durch die Ausgangsfunktion
Welche zwei Varianten gibt es für die Umsetzung der Ausgangsfunktion eines endlichen Automaten?	die Ausgabezeichen nur aus dem aktuellen Zustand ableiten und oder dabei zusätzlich das aktuelle Eingabezeichen einzubeziehen.
Wie nennt man einen endlichen Automaten, bei dem die Ausgangsfunktion nur vom aktuellen Zustand abhängt?	zustandsbasierter Automat bzw. Moore-Automat
Wie nennt man einen endlichen Automaten, bei dem die Ausgangsfunktion f sowohl vom aktuellen Zustand als auch von den aktuellen Eingabezeichen abhängt?	übergangsbasierter endlicher Automat oder Mealy-Automat
Wie sieht die Ausgangsfunktion eines Moore-Automaten formal aus?	f : S → O
Wie sieht die Ausgangsfunktion f eines Mealyautomaten aus?	f : S × I →O
Sei ein FSM durch ein (binäres) Schaltwerk realisiert, wie berechnet sich dann die Menge der möglichen Eingabezeichen, Zustände und Ausgabezeichen?	Als kartesisches Produkt der beiden jeweils möglichen Zustände: \( I ={0,1}^m \) \( S = {0,1}^k \) \(O = {0,1}^n \)
Wann nennt man einen endlichen Automaten "vollständig"?	wenn für jeden Zustand und alle möglichen Eingaben Zustandsübergänge (Kanten) spezifiziert sind.
Wann nennt man einen endlichen Automaten "widerspruchsfrei"?	wenn für jeden Zustand und alle möglichen Eingaben jeweils ein eindeutiger Folgezustand bestimmt ist
Welche Eigenschaft muss die Übergangsfunktion g aufweisen, damit ein endlicher Automat widerspruchsfrei ist?	g muss eine Funktion im engeren (mathematischen) Sinne sein. "pure function" bei gleicher Eingabe stets gleiche Ausgabe
Was muss für den jeweiligen Zustand \( S^{i}\) und \( S^{i+1} \) bei der Realisierung einer FSM durch ein Schaltwerk gelten, damit eine korrekte Arbeitsweise gewährleistet ist?	Die beiden Zustände müssen von einander entkoppelt sein.
Wie wird innerhalb eines Schaltwerks zur Realisierung einer FSM erreicht, dass Zustand und Folgezustand voneinander entkoppelt sind?	indem der Folgezustand stets durch nicht-transparente Speicherglieder (z.B. Register mit Master-Slave-Flipflops) realisiert wird
Welche zwei Darstellungsformen von Schaltwerken als FSM gibt es?	Zustandstabellen (bzw. -diagramme) und Zustandsgraphen
Wie ist eine Zustandstabelle zu einem Schaltwerk als endlicher Automat grundsätzlich aufgebaut?	linke Seite Eingabevariablen: Eingabevektor und Zustandsvektor rechte Seite Ausgangsvariablen: Folgezustandsvektor und Ausgangsvektor
Wie ist die Darstellung eines Schaltwerks als Zustandsgraph grundsätzlich aufgebaut?	Ein gerichteter Graph bestehend aus Knoten (Kreise) für die inneren Zustände und Kanten (Pfeile) für die Übergänge zwischen diesen Zuständen.
Was wird bei einem Zustandsgraphen eines Schaltwerkes grundsätzlich in die Knoten (Kreise) geschrieben?	Der Name des Zustands oder die Kombination der Zustandsvariablen
Was wird bei einem Zustandsgraphen eines Schaltwerkes grundsätzlich an die Kanten geschrieben?	die Belegung des Eingabevektors, die das Schaltwerk vom gegenwärtigen zum Folgezustand überführt
Was wird bei einem Mealyautomaten zusätzlich noch an die Kanten des Zustandsgraphen eines Schaltwerks geschrieben?	Die zu dem Zustand zugehörige Belegung des Ausgangsvektors
Wo wird bei dem Zustandsgraph eines Moore-Automaten die zu einem Zustand gehörende Belegung des Ausgangsvektors geschrieben?	In den Knoten des Zustands unterhalb des Bezeichners des Zustandes
Warum kann man bei einem Moore-Automaten die Kombination des Ausgabevektors in den Knoten schreiben?	weil bei diesem der Ausgabevektor eindeutig durch den momentanen Zustand bestimmt ist, d.h. die Ausgaben an allen ausgehenden Kanten des Knotens wären sowieso gleich
Hat der Zustandsvektor eines Schaltwerkes k Variablen, dann hat der entsprechende Zustandsgraph höchstens wieviele Knoten?	\( 2^k \)
Wieviele Kanten können in einem Zustandsgraph bei einem Eingabevektor mit m Komponenten maximal von jedem Knoten ausgehen?	\( 2^m \)
Welche Einschränkung bzgl. des Taktes besteht bei einem zu einem Mealy-Automaten äquivalenten Moore-Automaten?	dass im Vergleich zum Mealy-Automaten alle Ausgaben einen Takt verzögert erfolgen, und dass die Ausgabe im Startzustand nicht gewertet wird.
Warum erfolgen bei einem zu einem Mealyautomaten äquivalenten Moore-Automaten alle Ausgaben um einen Takt verzögert?	weil bei diesem die Eingabe während des ersten Taktes nur den Folgezustand beeinflussen kann und sich so erst im folgenden Takt auf die Ausgabe auswirkt
Wann kann man bei der Transformation einer Mealy- in eine Moore-FSM direkt den Wert der Ausgangsvariablen in den Knoten (im Moore-Graphen) schreiben?	Wenn im Mealy-Graph alle in den Knoten eingehenden Kanten die gleiche Ausgabe produzieren
Wieviele zusätzliche Knoten müsste man bei der Transformation einer Mealy-FSM in eine Moore-FSM bei unterschiedlichen Ausgabevariablen eingehender Kanten eines Knotens schaffen?	Für jede unterschiedliche Wertekombination des Ausgabevektors die an den eingehenden Kanten des Knotens im Mealy-Graph steht ein zusätzlicher Knoten im Moore-Graph
Wann muss man bei der Transformation eines Mealy- in einen Moore-Automaten zusätzliche Knoten(Zustände) schaffen?	Wenn sich bei den eingehenden Kanten eines Knotens im Mealy-Graph die zugehörigen Ausgabevariablen unterscheiden
Wie ermittelt man bei der Transformation eines Mealy- in einen Moore-Automaten bei den neu entstehenden Knoten die Ausgangvariablen?	Anhand der eingehenden Kanten aus dem Mealy-Automaten, die man ja dadurch ersetzt
Was müsste man zur Transformation eines Moore-Automaten in einen Mealy-Automaten an Änderungen im Zustandsgraph vornehmen?	Grds. nur die Übertragung der Ausgangsvariablen auf die eingehenden Kanten des jeweiligen Zustands
Wie kann man bei bei einem Zustandsgraphen überprüfen, ob man alle Kombinationen abgebildet hat?	Indem man für jeden Knoten überprüft, ob man für alle Möglichkeiten der Eingabevariablen ausgehende Kanten geschaffen hat.
Wenn es für ein Schaltwerk die Eingabevariablen 0 und 1 gibt, wieviele ausgehende Kanten muss dann jeder Knoten besitzen?	Immer zwei, 0 und 1

Nächster

3.3 Computersysteme I, Automatenmodelle für Schaltwerke

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von David Bratschke vor etwa 7 Jahre