Praktische Anwendung von Finite-State-Maschinen

Ich suche nach praktischen Anwendungen von Finite-State-Maschinen wie DFA-, NFA-, Moore-, Mealy-Maschinen ...

Es wäre hilfreich, wenn jemand auf Beispiele aus dem Linux-Kernel verweist. Ich weiß, dass DFA beim String-Matching wie beim KMP-Algorithmus verwendet wird.

Welche Bedeutung haben NFA-, Moore- und Mealy-Maschinen?

Jedes Mal, wenn Sie eine Suche (insbesondere eine "Mustersuche") in Ihrem bevorzugten Editor / Tool durchführen, wird das Muster in eine Form einer endlichen Zustandsmaschine übersetzt, die den Abgleich durchführt.

Der lexikalische Analyseteil Ihres Compilers / Interpreters (ja, sogar Ihrer Shell) ist wieder ein endlicher Automat, der Schlüsselwörtern und anderen von der Sprache erkannten Token entspricht.

Jeder Verkaufsautomat ist ein endlicher Automat, der Münzen mit unterschiedlichen Nennwerten aufnimmt und erkennt, wenn der richtige Betrag eingegeben wurde (OK, die heutigen Verkaufsautomaten haben wahrscheinlich eine kleine CPU im Inneren, die das Hinzufügen vornimmt, aber das Endergebnis ist das gleiche).

(die Konzepte von) DFA / NFA haben einige Anwendungen auf dem Gebiet der Compiler und beim Aufbau von Parsern. Sie werden auch verwendet, um Zeichenfolgen anhand regulärer Ausdrücke zu identifizieren (dh "Muster" über das Web oder über Datenbanken zu suchen).

Moore / Mealy-Maschinen sind DFAs, die ebenfalls zu jedem Zeitpunkt ausgegeben werden. Diese haben viele Anwendungen. Tatsächlich verfügt jede CPU, jeder Computer, jedes Handy, jede Digitaluhr und sogar Ihre Waschmaschine über eine Art Finite-State-Maschine, die sie steuert.

Vielleicht sollte ich klarstellen: Jeder "Computer" ist im Grunde eine endliche Zustandsmaschine.

Eine Hauptanwendung ist die Modellierung von Systemen. Im Wesentlichen können einfache Softwaresysteme als Finite-State-Maschinen modelliert werden. (Mit einfacher Software meine ich Sprachen, die mit regulären Ausdrücken dargestellt werden können). Es gibt viele solcher "einfachen" Systeme, Verkaufsautomaten sind Beispiele (wie vzn angegeben).

Indem Sie den Schnittpunkt zweier Finite-State-Maschinen finden, können Sie auf sehr einfache Weise gleichzeitig Systeme entwerfen, die beispielsweise Nachrichten austauschen. Beispielsweise ist die Ampel ein System, das aus mehreren Teilsystemen (den verschiedenen Ampeln) besteht, die gleichzeitig arbeiten.

Schauen Sie sich diese Beispiele an: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/

Sie benötigen einen LTSA-Analysator, um diese Beispiele ausführen zu können. http://www.doc.ic.ac.uk/ltsa/

Hier ist eine sehr gute Online-Referenz zu FSMs und verwandter Theorie, 75p, mit vielen Diagrammen. hat viele Anwendungen nach dem Abschnitt der mittleren Theorie und auch in vielen Übungen mit Beispielanwendungen, z. B. p485:

ch12. Finite-State-Maschinen von Keller, Harvey Mudd College, CS60 Lehrbuch / CS, Einführung in die Abstraktion

Anwendungen sind äußerst vielfältig. zB aus dem Buch:

• Nummernklassifizierung
• Uhr mit Timer
• Verkaufsautomat
• Ampel
• Barcodelesegerät
• Zapfsäule

Abschnitt 12.4 EE-Konstruktionen, z

• logische Elemente
• Taktquantisierung
• Kombinationsschloss
• Flip Flops
• Addierer
• Register
• Busse / Multiplexing

FSMs werden auch bei der Spracherkennung verwendet , um Phoneme zu finden. Dies ist einer der Hauptanwendungspunkte dieser hervorragenden Online-Bibliothek, die in Manpages und Dokumentationen einige Details enthält: AT & T Online-FSM-Bibliothek . siehe Abschnitt "FSM-Bibliotheks- und Sprachverarbeitungsanwendungen" (in dem auch einige abstraktere / theoretischere "Anwendungen" aufgeführt sind)

usw!

Ich benutze Zustandsautomaten beim Schreiben von Gerätetreibern. Beachten Sie, dass große Zustandsautomaten unhandlich werden können. Verwenden Sie diese Makros ( https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at ). Auf diese Weise werden die Übergänge so einfach, dass Sie dies nicht tun brauche sogar ein Zustandsdiagramm. Dies liegt daran, dass Sie mit den Makros Ihren Statusmaschinencode so schreiben können, als wäre er strukturierter Code. Mit diesen Makros habe ich die Transceiver Library von Cisco für das Nexus 7000 geschrieben.

In der Praxis sehen Sie es explizit als eine ganzzahlige Zustandsvariable (normalerweise als "Zustand" bezeichnet), die eine sehr grobe Zustandsmaschine darstellt, die darstellt, welche Aktionen vom Benutzer eines Objekts aufgerufen werden können. Es ist normalerweise eine Aufzählung mit Werten wie: {nicht initialisiert, initialisiert, ..., gestoppt}. Zustandsautomaten sind beim Parsen von Daten häufig explizit und werden durch eine switch-Anweisung in einer while-Schleife gekennzeichnet, in der am oberen Rand der Schleife das nächste Zeichen abgerufen wird. Insbesondere wenn das Parsen eine reguläre Grammatik hat, wird häufig ein genaues FSM ohne andere Funktionen verwendet. Wenn Sie sich in einer Sprache befinden, die Tail Calls unterstützt, werden FSMs im Allgemeinen durch gegenseitige Rekursion angezeigt (wodurch der Code wie eine sehr klare Pseudocode-Spezifikation gelesen werden kann). Eine wirklich nützliche Funktion eines FSM ist die Fähigkeit, gleichzeitig zu arbeiten, da Sie sich nur den aktuellen Status und nicht einen gesamten Ausführungsstapel merken müssen. (dh: Kontextwechsel zwischen Millionen von Zustandsmaschineninstanzen).