Automaten Flashcards
Was ist der Unterschied zwischen einem Schaltwerk und einem endlichen Automaten?
Sowohl Schaltwerk wie auch endlicher Automat entsprechen einer sequentiellen Maschine.
Schaltwerk und endlicher Automat können nur eine endliche Menge Zustände annehmen, zu einem bestimmten Zeitpunkt tn wird ein Eingabeelement x aus der endlichen Eingabemenge eingegeben.
Mit dem Zustand z gib der Automat das Ausgabeelement y der Ausgabemenge A aus. Dabei geht der Automat vom Zustand zi nach zj.
Die beiden Begriffe können synonym verwendet werden.
Welche Automatentypen gibt es und welche Besonderheit haben sie?
Medwedew-Automat - die Ausgabe Y ist gleich dem Automatenzustand Z, die Ausgabefunktion Lambda ist eine Identität
Moore-Automat - ermittelt die Ausgabefunktion ausschließlich aus den Zuständen, Lambda: Z -> A
Mealy-Automat - ermittelt die Ausgabe aus dem Zustand und den Eingaben des Automaten, Lambda: Z x E -> A
Was ist der wichtigste Unterschied zwischen dem Mealy- und Moore-Automaten
Mealy-Automat hängt von Zustand und externer Ausgabe ab, die Ausgabe ist daher asynchron.
Bei Moore ist die Ausgabe nur vom Zustand abhängig und erfolgt bei Zustandsänderung, die Ausgabe ist daher synchron.
Der Mealy-Automat kann daher schneller Reagieren als der Moore-Automat, der Moore-Automat ändert die Ausgabe erst nachdem der Takt vollständig vorbei ist und bleibt stabil, was besonders günstig für Zähler, Schieberegister oder Ampeln etc. ist
Wie verhalten sich die beiden Automaten zueinander?
Beide Automaten verhalten sich äquivalent zueinander und können ineinander überführt werden, vom Moore- zum Mealy-Automaten ist relativ einfach, von Mealy zu Moore müssen neue Zustände eingeführt werden, um die neuen Ausgabecharakteristik nachbilden zu können. Zusätzlich müsste man die Schaltfrequenz erhöhen um die Reaktionsfähigkeit eines Mealy Automaten mit einem Moore zu erreichen.
Wann ist ein Automat endlich?
Er ist endlich wenn das verwendete Eingabealphabet E, das Ausgabealphabet A und die Zustandsmenge S nichtleer und endlich sind
Wann ist ein Automat deterministisch?
Ein Automat ist deterministisch, wenn es für jede Kombination von Eingabezeichen und Zustand nur eine mögliche Kombination von Ausgabezeichen und Folgezustand gibt
Was ist ein Transduktor und was ein Akzeptor?
Ein Transduktor ist ein Automat, der ein Zeichen aus dem Eingabealphabet in Zeichen aus dem Ausgabealphabet überführt.
Ein Akzeptor wäre ein Automat, welcher keine Ausgabe besitzt, sondern akzeptierende Zustände aufweist.
Was ist die Grundidee hinter der Minimierung von Automaten?
Es gilt zwei Zustände zi und zj sind dann äquivalent, wenn jede beliebige Eingabezeichenfolge eine gleiche Ausgabenzeichenfolge herrvorruft, unabhängig davon, ob M im Zustand zi oder zj ist.
Die Menge von äquivalenten Zuständen werden als Äquivalenzklassen gruppiert.
Wie minimiert man Automaten mit der Zerlegung Pii?
Die Zerlegung Pii1 fasst alle Zustände zu Äquivalenzklassen zusammen, die identische Ausgaben für alle Eingaben der Länge 1 produzieren.
Pii k ist eine Zerlegung, die alle Zustände zusammenfasst, die die gleichen Ausgabenfolgen für alle Eingabenfolgen der Länge k produzieren.
Welche zwei Regeln kann man für die Minimierung verwenden?
Regel 1: Zustände zi und zj produzieren die gleichen Ausgabefolgen für alle Eingangsfolgen der Länge 2 genau dann, wenn diese in derselben Äquivalenzklasse liegen und die nächsten Zustände für jede Eingangsspalte x in derselben Äquivalenzklasse von Pii 1 liegen.
Regel K: für die Zustandstabelle von M lassen sich die Zustände zj und zi in Pii k+1 genau dann zusammenfassen, wenn zi und zj in derselben Äquivalenzklasse Pii k liegen und der nächste Zustand für jede Eingabespalte x in derselben Äquivalenzklasse von Pii k liegen
Wann ist die Minimierung abgeschlossen?
Die Minimierung ist abgeschlossen sobald Pii k+1 = Pii k ist und es keine weiteren Spezialisierungen gibt
Wie lauten die Regeln für den Entwurf von Automaten?
Entsprechen den Regeln für den Entwurf von Schaltwerken
