Wie unterscheidet sich eine Zustandsmaschine von anderen Computerprogrammen?

Ich habe mehrere Implementierungen von "State Machines" auf Github gesehen. Soweit ich weiß, nimmt eine Zustandsmaschine Eingaben entgegen, die ihren Zustand in einen endlichen Satz anderer Zustände umwandeln können oder nicht. Wie unterscheidet sich das von jedem anderen Computerprogramm?

Wenn Sie wirklich pedantisch sein wollen, ist jedes Computerprogramm eine endliche Zustandsmaschine, denn selbst wenn Sie alle Materie im gesamten Universum in einen Computer umwandeln, hat sie immer noch nur einen endlichen Speicher, also eine endliche Anzahl von Zuständen und eine endliche Anzahl der Übergänge zwischen diesen Zuständen.

Zustandsmaschinen sind Modelle wie Lambda-Kalkül, Turingmaschinen, Maschinen mit wahlfreiem Zugriff, Akteursysteme, Objektsysteme usw. Einige Probleme lassen sich von einer Zustandsmaschine modellieren, andere nicht.

Geschäftsprozesse wurden oft als Zustandsmaschinen modelliert, noch bevor Computer existierten. Sie eignen sich natürlich für diese Art des Denkens.

Aus theoretischer Sicht ist das überhaupt nicht anders. Aus theoretischer Sicht können Sie natürlich jedes Programm in Assemblersprache schreiben, und es funktioniert genauso gut.

Während der Computer, auf dem Ihr Code ausgeführt wird, mathematisch einer sehr, sehr komplizierten Zustandsmaschine entspricht, wie jedes andere Programm, das auf einem anderen Computer ausgeführt wird, gibt es viele Probleme, deren eleganteste Lösung eine einfache endliche Zustandsmaschine ist, deren Zustände und Übergänge haben domänenspezifische Bedeutungen, die der Programmierer entwickelt hat (im Gegensatz zum Compiler oder dem Hardware-Designer).

Eine klassische Methode zum Implementieren regulärer Ausdrücke besteht beispielsweise darin , den regulären Ausdruck als Spezifikation für eine endliche Zustandsmaschine zu interpretieren, eine solche Maschine zu erstellen und sie dann mit Zeichenfolgen zu versehen, um sie zu akzeptieren oder abzulehnen . Im Allgemeinen ist das Erstellen einer Zustandsmaschine möglicherweise die eleganteste Lösung , wenn Sie möchten, dass ein Objekt in Ihrem Programm immer einen endlichen Zustand aufweist und dass Übergänge zwischen diesen Zuständen immer auf bestimmte Weise erfolgen .

Eine Zustandsmaschine nimmt Eingaben entgegen, die ihren Zustand in einen endlichen Satz anderer Zustände umwandeln können oder nicht. Wie unterscheidet sich das von jedem anderen Computerprogramm?

Einige Antworten hier betonen, dass in unserem (wahrscheinlich) endlichen Universum alles endlich ist, alle Computerprogramme in endlicher Zeit ausgeführt werden, daher ist technisch alles eine endliche Zustandsmaschine. Das ist "technisch korrekt (die beste Art von richtig)", aber es fehlt auch völlig der Punkt.

Das Wesentliche ist Folgendes: - Einige Computerprogramme benötigen mehr Arbeitsspeicher, wenn sie größere und komplexere Eingaben erhalten. Einige tun es nicht.

Wenn Sie dies erkennen, erhalten Sie einen theoretisch-informatischen Einblick, der es Ihnen ermöglicht, effizientere und elegantere Programme zu schreiben, wenn Sie auf ein bestimmtes Problem stoßen. Außerdem können Sie die Art des Problems erkennen, bei dem dies auftreten kann.

Hier sind zwei Spielzeugbeispiele:

Problem 1: Ein Programm empfängt eine Liste von Zeichen bei Standardeingabe. Nachdem alle Zeichen verarbeitet wurden, muss das Programm drucken, ob die Anzahl der "x" -Zeichen in der Eingabe ungerade oder gerade war .

Problem 2: Ein Programm empfängt eine Liste von Zeichen bei der Standardeingabe. Nachdem alle Zeichen verarbeitet wurden, muss das Programm drucken, ob die Anzahl der "x" -Zeichen in der Eingabe kleiner , gleich oder größer als die Anzahl der "y" -Zeichen war.

Möglicherweise möchten Sie jetzt aufhören zu lesen, die Probleme in Ihrer bevorzugten Programmiersprache (oder nur einem Pseudocode) lösen und später zurückkehren.

...

Das Wichtige, was Sie vielleicht bemerkt haben, ist Folgendes: Um die Lösung für Problem 1 richtig zu implementieren, benötigen Sie nur ein Bit Speicher. Sie müssen nicht berechnen, wie viele "x" Sie bereits verarbeitet haben - nur, ob die Anzahl der bisher verarbeiteten "x" ungerade oder gerade war. Wenn Sie auf ein anderes "x" stoßen, drehen Sie das Bit um. Schauen Sie sich am Ende des Programms das Bit an und drucken Sie die Antwort aus.

Enthält Ihre Eingabe ein Dutzend Zeichen? Tausende von Charakteren? Googolplex-Charaktere (natürlich hypothetisch)? Macht nichts; Ein bisschen Arbeitsspeicher reicht noch aus.

Mit Problem 2 können Sie nicht dasselbe tun. Beim Lesen der Zeichen müssen Sie sich an den Unterschied zwischen der Anzahl der bereits verarbeiteten "x" und "y" erinnern. Andernfalls können Sie die richtige Antwort nicht zuverlässig drucken. Sie können erkennen , dass Sie tatsächlich nicht daran zu erinnern , müssen beide die Zahlen von „x“ ‚s und‚y‘‘ s - nur ihre Differenz, so weit; Ein ganzzahliger Wert, den Sie erhöhen, wenn Sie auf ein anderes "x" stoßen, und verringern, wenn Sie auf ein anderes "y" stoßen. Wenn Sie sich jedoch dazu entschließen, z. B. 32 Bit Speicher zu verwenden, um diesen Wert beizubehalten, erhalten Sie möglicherweise eine Eingabe ( mehrere Milliarden Zeichen lang), die Sie mit der angegebenen begrenzten Speichermenge nicht richtig verarbeiten können.

Dies ist es, was wir damit meinen, dass das Problem 1 von einer "Zustandsmaschine" gelöst werden kann und das Problem 2 nicht. Eine begrenzte Speichermenge reicht für eine Eingabe beliebiger Größe.

(Natürlich könnten Sie auch eine ineffiziente Lösung für das Problem 1 schreiben, bei der Sie versuchen würden, alle "x" zu zählen, und dann könnten Sie auch ein Problem mit zu wenig Speicher bekommen. Aber der Unterschied ist, dass ein effiziente Lösung für das Problem 1 besteht , während eine ähnlich effiziente Lösung für das Problem 2 funktioniert nicht .)

Warum ist das im wirklichen Leben wichtig?

Erstens liegt das Dilemma im Gegensatz zu diesen beiden Spielzeugbeispielen möglicherweise nicht zwischen buchstäblich einem Bit und einem ganzzahligen Wert, sondern zwischen einer großen und einer noch größeren Datenstruktur. Manchmal passt die "noch größere" Datenstruktur nicht in den Computerspeicher oder verlangsamt das Programm ausreichend, selbst für realistische Eingaben.

Zweitens wird die Lösung mit der Zustandsmaschine wahrscheinlich viel schneller sein. Außerdem wird es linear mit der Länge der Eingabe skaliert . Das heißt, die Verarbeitung einer 10-mal längeren Eingabe erfordert 10-mal mehr Zeit (im Gegensatz zu beispielsweise 100-mal mehr Zeit). Dies ist eine gewünschte Eigenschaft, wenn Sie viele Daten verarbeiten müssen.

Drittens wirkt sich eine begrenzte oder unbegrenzte Speichernutzung auf die Sicherheit aus . Wenn Sie ein Programm schreiben, das nur begrenzten Speicher benötigt, müssen Sie sich keine Gedanken über Speicherüberläufe machen und darüber, wie diese möglicherweise missbraucht werden können, um die Sicherheit des gesamten Systems zu gefährden.

Viertens ist dies Teil eines Standardlehrplans für Informatik in jeder anständigen Schule: formale Sprachen , Authome , Komplexität der Berechnungen usw. Um das Gesamtbild hinter dem Computerdesign zu verstehen, im Gegensatz zu "ähm, ich habe einige Codeteile aus dem Internet zusammengestellt, hoffe ich wirklich, dass es funktioniert, aber ich kann es nicht sicher sagen".

Um diese Theorie zu nutzen, brauchen Sie keine spezielle Maschine, kein Framework oder keine Bibliothek ... Sie müssen nur erkennen, "oh, dieser Teil des Problems kann tatsächlich mit einer begrenzten Menge an Speicher gelöst werden" und schreiben Ihr Programm (in Ihrer bevorzugten Programmiersprache) entsprechend. In einigen Situationen ist es jedoch besser, eine vorhandene Bibliothek zu verwenden, damit Sie das Rad nicht neu erfinden müssen.

Wie die anderen Antworten zeigten, sind Zustandsautomaten nichts Besonderes. Es ist jedoch häufig von Vorteil, ausdrücklich anzugeben, dass unser Programm einen FSM implementiert.

Die Programmierung besteht darin, geeignete Abstraktionen für ein Problem zu finden. Die Verwendung einer Abstraktion bedeutet, eher in Bezug auf die Abstraktion als in Bezug auf die Implementierung zu sprechen. Viele Prozesse sind von Natur aus statusbehaftet, z. B. der Anmeldevorgang auf einer Website oder der Check-out-Vorgang in einer E-Commerce-Anwendung. Wenn ich diese Prozesse modellieren würde, würde ich durch Pfeile verbundene Kästchen auf ein Whiteboard zeichnen - ein Zustandsdiagramm. Hier wäre eine Zustandsmaschine eine Art Entwurfsmuster, und wenn ich über Zustandsmaschinen spreche, würde dies meine Absicht den Kollegen klar mitteilen.

Imperative Programme sind von Natur aus zustandsbehaftet, sodass wir nicht immer bemerken, wenn wir state einführen. Beispielsweise markieren in der C-Sprache bestimmte Sprachkonstrukte wie der Semikolonoperator einen "Sequenzpunkt", der einen Zustandsübergang darstellt und die Reihenfolge zwischen Operationen erzwingt. In Umgebungen wie reinen Funktionssprachen wie Haskell oder bei Verwendung zustandsloser Protokolle wie HTTP sieht das anders aus. Plötzlich muss jeder Zustand explizit werden, und die explizite Formulierung unseres Entwurfs als Zustandsmaschine kann ihn überschaubarer machen.

Finite-State-Maschinen spielen beim Parsen eine wichtige Rolle, da sie regulären Ausdrücken entsprechen. Das manuelle Implementieren eines regulären Ausdrucks kann zu extrem haarigem Code führen, der im schlimmsten Fall nicht einmal korrekt ist. Wenn wir feststellen, dass wir eine Zustandsmaschine implementieren, können wir verschiedene bekannte Implementierungstechniken verwenden, um uns zu helfen. Zum Beispiel könnten wir den Status explizit machen und den aktuellen Status in einer Variablen speichern. Alternativ können wir den Zustand implizit machen, indem wir unsere Sprache steuern. Ich habe beides unter verschiedenen Umständen getan, aber festgestellt, dass wir eine Zustandsmaschine implementieren (die eingeschränkte Zustandsübergänge, einen Startzustand, bekannte Endzustände, keine Rekursion und keinen impliziten Zustand durch persistente Datenzuweisung aufweist), anstatt ein uneingeschränktes Programm zu erstellen es ist einfacher zu implementieren und zu verstehen.

Ich würde selten eine Zustandsmaschinenbibliothek verwenden, da alle mir bekannten Programmiersprachen es einfach machen, eine Zustandsmaschine in dieser Sprache korrekt und effizient auszudrücken. Es gibt jedoch Ausnahmen: Während deterministische Automaten einfach zu implementieren sind, sind nichtdeterministische Automaten nicht trivial, da sich die Zustandsmaschine gleichzeitig in mehreren Zuständen befinden kann. Wenn ich eine Bibliothek verwende, die NFAs implementiert oder neu schreibt, kann ich diese Schwierigkeiten ignorieren und mich auf Dinge konzentrieren, die wirklich wichtig sind.

Abgesehen von der Verwendung von Zustandsmaschinen als Entwurfs- und Zustandsmaschinen in der Informatik und Sprachtheorie gibt es nicht wirklich so viele Verwendungen. Stateful Logic-Schaltungen kommen in den Sinn. Die Hauptanwendung von Zustandsautomaten für einen Programmierer ist das Lernen, in Zuständen und Zustandsübergängen zu denken. Wo hat mein Programm implizite Zustände? Habe ich alle Zustandsübergänge korrekt implementiert? Habe ich etwas verpasst und einen ungültigen Zustand eröffnet? Ein solches Denken wird in der objektorientierten Programmierung wieder besonders relevant, da die Mitgliedsfelder eines Objekts dem Zustand entsprechen und Methoden Zustandsübergänge bewirken können. Ich würde zögern, eine Zustandsmaschine explizit in einem Objekt zu implementieren, aber eine Zustandsmaschine kann dennoch ein geeignetes mentales Modell für das Verhalten sein.

Der Hauptgrund für das Schreiben einer Zustandsmaschinenbibliothek besteht darin, sicherzustellen, dass Sie das Thema verstanden haben. In den meisten Anwendungen würden Sie sie jedoch nicht benötigen oder vielmehr von Hand rollen.