Was sind Finite State Automata und warum sollten sie über ein Programmierer wissen?

StackOverflow https://stackoverflow.com/questions/364193

  •  21-08-2019
  •  | 
  •  

Frage

Erm - was die Frage sagte. Es ist etwas, was ich höre immer wieder, aber ich habe nicht dazu gekommen zu schauen hinein vor.

(aktualisiert) Ich könnte die Definition nachschlagen ... aber warum nicht (wie von @erikson weist darauf hin) erhält Einblick in Ihre realen Erfahrungen und Anekdoten. Gemeinschaft Wiki'd einhüllen, das hilft Menschen, die aufschlussreiche Antwort abstimmen werden. Interessante Lektüre so weit, Dank!

War es hilfreich?

Lösung

Kurze Antwort, es ist eine Technik, die Sie zum Ausdruck bringen Systeme mit konkreten Staaten nutzen können (im Gegensatz zu Quantenzuständen / Wahrscheinlichkeitsverteilungen gegen).

die Wikipedia-Artikel Zitiert:

  

Eine Finite State Machine (FSM) oder finite   Automat (Plural: Automaten) oder   einfach eine Zustandsmaschine, ist ein Modell der   Verhalten einer endlichen Anzahl zusammengesetzt   von Zuständen, Übergänge zwischen jenen   Zustände und Handlungen. Ein endlicher   Maschine ist ein abstraktes Modell eines   Maschine mit einem primitiven internen   Speicher.

Also, was das für Sie bedeutet? Einfach gesagt, ist es ein effektiver Weg, den Weg zu repräsentieren (e) von einem Ausgangszustand in den Endzustand (n) des Systems, die Sie interessieren. Verwenden von regulären Ausdrücken als ziemlich einfaches Beispiel zu verstehen, wollen wir uns die Muster aussehen AB + C (sich vorstellen, dass das plus ein Exponent ist). Ich würde wieder in dieses Muster erwartet Strings wie „ABC“, „ABBC“, „ABBBC“ usw. A am Anfang, C am Ende, einen gewisse Anzahl von B in der Mitte (größer oder gleich eins) zu akzeptieren .

Wenn man darüber nachdenkt, ist es fast leichter, über das in Bezug auf ein Bild zu denken. Faking es mit Text (und das meine Klammern ein Loopback-Bogen) sind, können Sie sehen, dass A (links), ist der Ausgangszustand und C (rechts) ist der Endzustand auf der rechten Seite. 

      _
     ( ) 
A --> B --> C

Von FSAs, können Sie Ihre Reise in der Rechenkomplexität weiterhin in das Land Überschrift über die Turingmaschinen .

Sie können jedoch auch Zustandsmaschinen verwenden, um reale Verhalten und Systeme darstellen. In meiner Welt, sie verwenden wir bestimmen Workflow von tatsächlichen Menschen mit Komponenten arbeiten zu modellieren, die extrem intolerant von Fehlern in staatlicher Ordnung sind. Wie in „Ein besser vor C geschehen war oder es wird ein sehr ernstes Problem sein. Dass seine Make jetzt nicht möglich.“

Andere Tipps

Sie könnte schauen Sie, aber zum Teufel was. Intuitiv ein endlicher Automat ist eine Abstraktion von etwas, das eine endliche Anzahl von Zuständen hat, und Regeln, nach denen Sie sich von Staat zu Staat gehen kann. A Zustand ist etwas, für das eine wahre oder falsche Aussage gemacht werden kann, und in der Regel ist eine Art und Weise, die Sie von einem Zustand in einen anderen zu wechseln. So könnte man sagen, zwei Zustände: „nach Hause gehen“, „Ich bin zu Hause“ und „Ich bin bei der Arbeit“ und zwei Regeln „zur Arbeit gehen“ und

Es stellt sich heraus, dass man mathematisch an Maschinen wie folgt aussehen können, und finden es gibt Dinge, die sie können und nicht tun können. Reguläre Ausdrücke sind im Grunde eine Art und Weise einen endlichen Automaten zu beschreiben, in dem die Zustände sind eine Reihe von verschiedenen Saiten, und die Regeln bewegen Sie sich von Staat zu Staat, basierend auf dem nächsten Zeichen lesen. Sie können das beweisen. Sie können aber auch beweisen, dass keine endlichen Automaten kann sagen, ob die Klammern in einem Ausdruck aufeinander abgestimmt sind (über die Pumping-Lemma FSAs.)

Der Grund, warum Sie sollten lernen über FSAs ist, dass sie verwendet werden kann, viele Probleme zu lösen: String-Matching, Steuerung von Systemen, Geschäftsprozessbeschreibungen, digitalen Schaltungsdesign. Sie sind auch von Natur aus schön.

Formal , eine von der FSA ist eine algebraische Struktur F = ⟨Σ, S, s 0 , F, δ⟩ , wobei Σ der Eingabealphabet S ist eine Reihe von Staaten s 0 ∈ S ist eine besondere Startzustand F ⊆ S ist eine Reihe von zu akzeptieren Staaten und δ: S × Σ → S die Zustandsübergangsfunktion .

in OOP Bedingungen: Wenn Sie ein Objekt mit Methoden haben, die Sie auf bestimmte Ereignisse nennen, und einige (andere) Methoden, die unterschiedliche Verhalten auf den vorherigen Anrufe je .... überraschen! Sie haben eine Zustandsmaschine!

jetzt, wenn Sie die Theorie kennen, müssen Sie es nicht überdenken alles. Sie einfach sagen: „Stück Kuchen, es ist nur eine Zustandsmaschine“ und gehen auf sie implementieren

.

Wenn Sie nicht wissen, die Theorie Sie es für eine Weile denken werden, schreiben einige cleveren Hacks, und etwas, das schwer zu erklären und zu dokumentieren ... weil Sie es nicht die Worte zu beschreiben

Sie müssen Zustandsmaschinen, wenn Sie Ihren Thread lösen, bevor Sie Ihren Betrieb abgeschlossen haben.

Da Web-Service wird oft nicht zuzustandsbehaftete, müssen Sie in der Regel nicht das sieht in Web-Service -. Sie Ihre URL neu ordnen, so dass jede URL zu einem einzigen Pfad durch den Code entspricht

ich denke, eine andere Art und Weise zu denken, dass jeder Web-Server könnte eine FSM ist, wo die Zustandsinformationen in der URL gehalten.

Sie sehen es oft, wenn die Eingabe der Verarbeitung. Sie haben Ihren Thread zu lösen, bevor die Eingabe beendet alle wurde, so legen Sie ein Flag „Eingang in progress“ oder so etwas zu sagen. Wenn Sie fertig stellen Sie das Flag auf „Eingang wartet“. Diese Flagge ist Ihr Zustand Monitor.

Mehr als oft nicht, wird ein FSM als switch-Anweisung implementiert, die auf eine Variable schaltet. Jeder Fall ist ein anderer Zustand. Am Ende des Falles können Sie den Zustand auf einen neuen Wert gesetzt. Sie haben mit ziemlicher Sicherheit das irgendwo gesehen.

Das Schöne an einer FSM ist, dass man den Staat einen Teil Ihrer Daten machen kann, anstatt Ihr Code. Stellen Sie sich vor, dass Sie 1000 Elemente in der Datenbank ausfüllen müssen. Die eingehenden Daten werden einer der 1000 Elemente adressieren, aber Sie haben in der Regel nicht genug Daten, um die Operation abzuschließen.

Ohne FSM könnten Sie Hunderte von Threads um für den Rest der Daten warten, so dass sie die Verarbeitung durchführen können und die Ergebnisse an die DB schreiben. Mit einer FSM, schreiben Sie den Zustand der DB, dann Thread beenden. Das nächste Mal können Sie die eingehenden Daten überprüfen, lesen Sie den Zustand aus dem Thread und das sollte man genug Informationen geben, um zu bestimmen, welcher Code ausgeführt werden.

Fast jeder FSM Betrieb könnte durch widmen einen Thread es getan werden, aber wahrscheinlich nicht so gut (Die vervielfacht Komplexität basierend auf der Anzahl von Staaten, während bei einer Zustandsmaschine der Anstieg der Komplexität mehr linear ist). Auch gibt es einige konzeptionellen Design-Fragen - Code auf der staatlichen Ebene der Prüfung in einigen Fällen ist viel einfacher, als es auf der Linie der Code-Ebene untersuchen

.

Gute Antworten oben. Ich würde nur hinzufügen, dass FSA ist in erster Linie ein Denken Werkzeug , keine Programmiertechnik. Was macht sie nützlich ist sie schön Eigenschaften haben, und alles, was wie man diese Eigenschaften wirkt. Wenn Sie etwas als FSA denken kann, gibt es viele Möglichkeiten, wie Sie es bauen können:

  • als regulärer Ausdruck

  • als Zustandsübergangstabelle

  • als while-Einschalt-Zustand-Loop

  • als goto-net (Schrecken!)

  • als einfach strukturierte Programmcode

usw. etc.

Wenn jemand etwas sagt, ist ein FSA, können Sie sofort wissen, was sie reden, egal wie es gebaut wird.

Jeder Programmierer sollte über sie weiß, weil sie ein ausgezeichnetes Werkzeug für bestimmte Arten von Problemen sind, wo der üblicher ‚iterativ-Denken‘ -Ansatz bös, komplexen Code ergeben würde.

Ein typisches Beispiel ist Spiel AI, wo NPCs unterschiedliche Zustände haben, die nach ändern, wo der Spieler ist, so etwas wie:

  • NPC_STATE_IDLE
  • NPC_STATE_ALERT (Spieler bei weniger als 100 Meter)
  • NPC_STATE_ENGAGE (Spieler angegriffen NPC)
  • NPC_STATE_FLEE (auf die Gesundheit niedrig)

, wo ein FSM leicht die Übergänge beschreiben können und helfen, führen komplexe Argumentation über das System der FSM beschreibt.

. Wichtig: Wenn Sie ein „visual“ Stil Lerner, stoppt alles, was Sie und ... Right Now zu diesem Link gehen tun

Wenn Sie ein „visuellen“ Lerner sind, ist hier eine ausgezeichnete Verbindung, die eine sehr zugängliche Einführung gibt.

Reanimator von Oliver Steele

Es sieht aus wie Sie bereits eine Antwort genehmigt haben, aber wenn Sie „visual“ Einführung in neue Konzepte zu schätzen wissen, wie es üblich ist, sollten Sie wirklich den Link sehen. Es ist einfach hervorragend.

(Hinweis: Der Link verweist auf eine Diskussion von DFA und Ndfa im Rahmen von regulären Ausdrücken - mit animierten interaktiven Diagrammen)

Was ist es besser auf anderen Seiten beantwortet (zB Wikipedia), weil es ziemlich umfangreiche Antworten sind da draußen schon.

Warum sollten Sie sie kennen. Da Sie wahrscheinlich sie bereits umgesetzt

Jedes Mal, wenn Ihr Code eine begrenzte Anzahl von möglichen Zuständen hat (das ist der „finite state“ Teil) und schaltet auf einen anderen einmal eine Eingabe / Ereignis geschieht (das ist der „Maschine“ Teil) Sie ein endlicher Automaten geschrieben habe .

Es ist ein sehr übliches Werkzeug und die theoretischen Grundlagen für das zu wissen, in der Lage zu sein, darüber zu argumentieren und zu wissen, wie zwei FSMs zu einem einzigen zu kombinieren, die die gleichen Arbeit tun kann eine große Hilfe sein.

FSAs sind große Datenstrukturen zu verstehen, weil jede Chance, dass Sie sie umsetzen müssen, sind Sie auf der untersten Ebene der Rechenkomplexität auf der Chomsky-Hierarchie arbeiten. Ein gutes Beispiel ist in Wort Morphologie (wie Teile von Worten zusammen kommen). Viel Arbeit wurde getan, um zu zeigen, dass selbst die schwersten Fällen kann in dieser extrem schnellen analytischen Rahmen analysiert werden. Werfen Sie einen Blick auf Karttunnen und Beesley Arbeit aus PARC.

FSAs ist auch ein großartiger Ort beginnen Lernen über maschinelles Lernen Konzepte wie Hidden-Markov-Modelle, weil in vielerlei Hinsicht kann das Problem nach unten mit den gleichen Ideen und Vokabular gebrochen werden.

Ein Element, das bisher noch nicht erwähnt wird, ist die semantische Äquivalenz von endlichen Automaten und reguläre Ausdrücke. Ein regulärer Ausdruck kann auf einen endlichen Automaten kompiliert werden (dies ist, wie regex Bibliotheken arbeiten) und umgekehrt.

FSA (einschließlich DFA und NFA) sind sehr wichtig für Informatik und sie sind den Einsatz in vielen Bereichen, einschließlich vielen Bereichen. So versteckt markov Felder für die Spracherkennung werden auch reguläre Ausdrücke der FSA umgesetzt, bevor sie werden von der Software und NLP (Natural Language Processing), AI (Spiele-Programmierung), Roboterprogrammierung usw.

interpretiert

Ein Nachteil der FSA sind sie in der Regel nur langsam und in der Regel schwer zu implementieren und schwer zu verstehen oder zu visualisieren, während Sie den Code zu lesen, aber sie sind gut, weil sie in der Regel generische Lösungen für die Probleme bieten und sie sind bekannt mit viele Studien über die FSA.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top