Karteikarten
3.3 Computersysteme I, Automatenmodelle für Schaltwerke
Karten in diesem Stapel (37)
- 1Was ist ein "Automat"?ein Modell für ein diskretes, zeitveränderliches System.
- 2Wie 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 - 3Wann spricht man von einem endlichen Automaten?Wenn
das Eingangsalphabet,
die Menge der Zustände und
das Ausgabealphabet
endlich sind. - 4Was ist das Eingabe-/Ausgabealphabet?die Menge der möglichen
Eingabe-/Ausgabezeichen - 5Wie wird ein endlicher Automat noch genannt? (Englisch)Finite State Machine (FSM)
- 6Was 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 - 7Durch welche Funktion werden bei einem Automaten die Ausgabezeichen bestimmt?Durch die Ausgangsfunktion
- 8Welche 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. - 9Wie nennt man einen endlichen Automaten, bei dem die Ausgangsfunktion nur vom aktuellen Zustand abhängt?zustandsbasierter Automat
bzw.
Moore-Automat - 10Wie 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 - 11Wie sieht die Ausgangsfunktion eines Moore-Automaten formal aus?f : S → O
- 12Wie sieht die Ausgangsfunktion f eines Mealyautomaten aus?f : S × I →O
- 13Sei eine endlicher Automat 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 \) - 14Wann nennt man einen endlichen Automaten "vollständig"?wenn für jeden Zustand und alle möglichen Eingaben Zustandsübergänge (Kanten) spezifiziert sind.
- 15Wann nennt man einen endlichen Automaten "widerspruchsfrei"?wenn für jeden Zustand und alle möglichen Eingaben jeweils ein eindeutiger Folgezustand bestimmt ist
- 16Welche Eigenschaft muss die Übergangsfunktion g aufweisen, damit ein endlicher endlicher Automat widerspruchsfrei ist?g muss eine Funktion im engeren (mathematischen) Sinne sein.
"pure function"
bei gleicher Eingabe stets gleiche Ausgabe - 17Was 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.
- 18Wie 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 - 19Welche zwei Darstellungsformen von Schaltwerken als FSM gibt es?Zustandstabellen (bzw. -diagramme)
und
Zustandsgraphen - 20Wie ist eine Zustandstabelle zu einem Schaltwerk als endlicher Automat grundsätzlich aufgebaut?linke Seite Eingabevariablen:
Eingabevektor und Zustandsvektor
rechte Seite Ausgangsvariablen:
Folgezustandsvektor und Ausgangsvektor - 21Wie 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.
- 22Was wird bei einem Zustandsgraphen eines Schaltwerkes grundsätzlich in die Knoten (Kreise) geschrieben?Der Name des Zustands
oder
die Kombination der Zustandsvariablen - 23Was 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
- 24Was wird bei einem Mealyautomaten zusätzlich noch an die Kanten des Zustandsgraphen eines Schaltwerks geschrieben?Die zu dem Zustand zugehörige Belegung des Ausgangsvektors
- 25Wo 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 - 26Warum 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
- 27Hat der Zustandsvektor eines Schaltwerkes k Variablen, dann hat der entsprechende Zustandsgraph höchstens wieviele Knoten?\( 2^k \)
- 28Wieviele Kanten können in einem Zustandsgraph bei einem Eingabevektor mit m Komponenten maximal von jedem Knoten ausgehen?\( 2^m \)
- 29Welche 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.
- 30Warum 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
- 31Wann 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
- 32Wieviele 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
- 33Wann 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
- 34Wie 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
- 35Was 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
- 36Wie 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.
- 37Wenn es für ein Schaltwerk die Eingabevariablen 0 und 1 gibt, wieviele ausgehende Kanten muss dann jeder Knoten besitzen?Immer zwei,
0 und 1
Informationen
- Beschreibung
- Der Nutzer hat seine Fachbereichs-Information gelöscht. Karteikarten am 3.3 Computersysteme I, Automatenmodelle für Schaltwerke, erstellt von Gelöschter Nutzer am 10/04/2018.
- Erstellt von
- Gelöschter Nutzer · Apr 2018
- Aktualisiert
- 10 Apr 2018
- Aufrufe
- 13
- Verlauf
-
- Erstellt von David Bratschke · 25 Okt 2017
- Kopiert von Daniel Bratschke · 10 Apr 2018
- Bewertung