11060385
Description
Flashcards by David Bratschke, updated more than 1 year ago
|
Created by David Bratschke
over 6 years ago
|
|
| Question | Answer |
| 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.