Was ist der Unterschied zwischen endlichen Automaten und endlichen Zustandsautomaten?

16

Ich habe FSM in Digital Sequential Circuit-Designs verwendet. Endliche Automaten kenne ich aber nicht. Kann mir jemand helfen, den grundlegenden Unterschied zwischen beiden zu verstehen?

terminology automata finite-automata gpuguy
quelle
5
Aus Wikipedia : "... In der Automatentheorie ist ein Zweig der theoretischen Informatik, ein deterministischer endlicher Automat (DFA) - auch als deterministische endliche Zustandsmaschine bekannt - eine endliche Zustandsmaschine, die endliche Zeichenfolgen akzeptiert / ablehnt und nur erzeugt eine eindeutige Berechnung (oder Ausführung) des Automaten für jede Eingabezeichenfolge ... ". DFA ist der bevorzugte Begriff, der in der Automatentheorie verwendet wird, FSM ist der bevorzugte Begriff, der in praktischen Anwendungen verwendet wird.
Vor dem
4
Ich denke, FSM ist integrativer, einschließlich auch Mealy- und Moore-Automaten. NFA sind ein bestimmtes Modell.
Raphael
@Raphael: Ich stimme dir zu, FSM scheint breiter zu sein (sogar Wikipedia unterscheidet zwischen Transducern, Akzeptoren, Klassifikatoren und Sequenzern). "DFA" ~ "FSM-Akzeptoren" (FSM mit nur Ja / Nein-Ausgang) ... außerdem verwenden FSM in Schaltungsentwürfen normalerweise Ausgänge ... Vielleicht können Sie Ihren Kommentar in eine Antwort umwandeln.
Vor dem
Persönlich verwende ich FSM als weit gefassten Begriff, der DFA-, NFA-, Mealy- und Moore-Maschinen, (endliche) Wandler usw. umfasst. einfach alles mit einem endlichen Zustandsraum und ohne Hilfsspeicher.
Dan
1
@Raphael In der Formaltheorie (oder der Berechnungstheorie) bevorzugen wir das Wort "Automaten", um hervorzuheben, dass unsere Maschine eine "automatische" Maschine ist (selbstbewegend wie Ihr Computer) - "automatisch" in dem Sinne, dass es einmal war Wenn Sie Übergangsregeln definiert haben, müssen Sie keine expliziten intelligenten Regeln anwenden, um Zeichenfolgen zu verarbeiten / zu klassifizieren (Sie müssen lediglich bei jedem Schritt auf Übergangsregeln verweisen). - Während der Maschinenbegriff im Zusammenhang mit dem Gerät (und nicht dem Modell) bevorzugt wird - obwohl beide Synonyme voneinander sind.
Grijesh Chauhan

Antworten:

12

Soweit ich weiß, haben beide "Zustände" und "Aktionen", durch die die Maschine bei einem Eingangssignal von einem Zustand in einen anderen übergeht. Die konzeptionellen Ideen sind also dieselben. Es gibt einige Unterschiede in den Details.

In FSM für Schaltungsentwürfe wird das Eingangssignal meistens als ein Bit (binär) angenommen, wohingegen in Automaten mit endlichen Zuständen ein allgemeines "abstraktes" Alphabet von Eingangssymbolen vorliegen kann. Zweitens erzeugt ein FSM auch eine Ausgabe, die dem erreichten Zustand zugeordnet ist und ebenfalls binär ist. In der Terminologie der Automaten wird diese 'Erweiterung' als Moore-Maschine bezeichnet. Automaten haben jedoch endgültige (oder akzeptierende) Zustände, die ein günstiges Lesen der Eingabe signalisieren. Schließlich sind FSM meist deterministisch, dh für jede Eingabe in einem bestimmten Zustand gibt es einen nächsten Zustand. In der Automatentheorie betrachtet man auch die nichtdeterministische Variante, bei der man die Wahl hat, wohin man sich bewegen soll.

Hendrik Jan
quelle
6

Basierend auf meiner Erfahrung sowie dem Wikipedia-Artikel gibt es verschiedene Arten von Zustandsautomaten , einschließlich

Einige der Begriffe, die herumfliegen, unterscheiden sich hauptsächlich in der Motivation; Einige sind aus der Sprach- und / oder Berechenbarkeitstheorie hervorgegangen, andere aus der Computerarchitektur.

Beachten Sie, dass Sie auch mehrere Paradigmen ändern können, um beispielsweise Automaten zu erhalten, bei denen es sich möglicherweise noch um Automaten mit endlichen Zuständen handelt

Wie Sie sehen, handelt es sich bei den in TCS 101 gelehrten endlichen Vanilla-Automaten nur um eine Variante von vielen, die jeweils eine eigene (mehr oder weniger formale) Definition haben.

Raphael
quelle
2

Obwohl die Grundidee, auf die sich beide stützen, dieselbe ist. Beide verwenden endliche Zustände und springen in einen anderen Zustand als Eingabefeed. FSM ist jedoch eine Maschine wie ein Volladdierer oder ein SR-Flipflop und hat Bits als Ein- und Ausgang. Ja, FSA hat auch eine Bitausgabe, 0 für den nicht beendenden Zustand und 1 für den beendenden Zustand, aber es ist ein abstrakter Mechanismus und nicht zu sehen. Es gibt Unterschiede in den Digraphen, die gezeichnet werden, um sie darzustellen. Außerdem ist FSA ein Logik- und Rechengerät, während FSM ein digitales Logikgerät ist.

Saryan Sandeep
quelle