Definition endlicher Automaten. Finite-State-Maschinen Finite-State-Maschine im Steuerungsalgorithmus
Theorie endlicher Zustandsmaschinen
Die Automatentheorie liegt der Theorie der Compilerkonstruktion zugrunde. Ein endlicher Automat ist eines der Grundkonzepte. Mit Automat meinen wir etwas, das nicht wirklich existiert. technisches Gerät, obwohl ein solches Gerät gebaut werden kann, und ein mathematisches Modell, dessen Eigenschaften und Verhalten mit einem Programm auf einem Computer nachgeahmt werden können. Ein endlicher Automat ist das einfachste Modell der Automatentheorie und dient in der Regel als Steuergerät für alle anderen Automatentypen. Der endliche Automat hat eine Reihe von Eigenschaften:
· Eine Zustandsmaschine kann eine Reihe einfacher Kompilierungsprobleme lösen. Der lexikalische Block wird fast immer auf der Grundlage einer endlichen Zustandsmaschine aufgebaut.
· Der Betrieb des Finite-State-Automaten zeichnet sich durch hohe Leistung aus.
· Die Zustandsmaschinenmodellierung erfordert eine feste Speichermenge, was die Speicherverwaltung vereinfacht.
· Es gibt eine Reihe von Theoremen und Algorithmen, mit denen Sie endliche Automaten konstruieren und vereinfachen können.
In der Literatur gibt es verschiedene Definitionen einer endlichen Zustandsmaschine. Gemeinsam ist ihnen jedoch, dass die Finite-State-Maschine ein Rechengerät mit einer festen Speichermenge modelliert, das Sequenzen von Eingabesymbolen liest, die zu einem Eingabesatz gehören. Die grundlegenden Unterschiede in den Definitionen hängen davon ab, was die Maschine am Ausgang tut. Die Ausgabe der Maschine kann ein Hinweis darauf sein, ob eine bestimmte Eingabekette „akzeptabel“ ist oder nicht. „Akzeptabel“ ist eine korrekt aufgebaute oder syntaktisch korrekte Kette. Beispielsweise gilt eine Kette, die eine numerische Konstante darstellen soll, als falsch konstruiert, wenn sie zwei Dezimalstellen enthält.
Definition: Ein endlicher Automat ist ein formales System, das mithilfe der folgenden Objekte definiert wird:
· endlicher Satz von Eingabesymbolen;
· endliche Menge von Zuständen;
· eine Übergangsfunktion, die jedem Paar (aktueller Zustand, Eingabesymbol) einen neuen Zustand zuweist;
· Ausgangszustand;
· eine Untergruppe von Zuständen, die als permissiv oder endgültig gekennzeichnet sind.
Beispiel. Lassen Sie uns die Funktionsweise eines Controllers analysieren, der prüft, ob die Anzahl der Einsen in einer beliebigen Kette aus Nullen und Einsen gerade oder ungerade ist. Nehmen wir an, dass der entsprechende endliche Automat alle Ketten mit einer ungeraden Anzahl von Einsen „akzeptieren“ und Ketten mit einer geraden Anzahl „ablehnen“ muss. Nennen wir diese Maschine einen „Paritätscontroller“. Wir glauben, dass andere Symbole als 0 und 1 nicht an den Eingang der Maschine übermittelt werden können. Das Eingabealphabet des Controllers ist also die Menge (0, 1) . Wir glauben, dass der endliche Automat zu einem bestimmten Zeitpunkt nur ein Eingabesymbol verarbeitet und Informationen über die vorherigen Symbole der Eingabekette mithilfe einer endlichen Menge von Zuständen speichert. Wir betrachten die Menge (gerade, ungerade) als eine Menge von Zuständen; einer dieser Zustände muss als Anfangszustand ausgewählt werden. Sei es der Zustand (gerade), da im ersten Schritt die Anzahl der gelesenen Einsen Null ist und Null eine gerade Zahl ist. Beim Lesen des nächsten Eingabesymbols ändert sich der Zustand der Maschine entweder oder bleibt gleich, und sein neuer Zustand hängt vom Eingabesymbol und dem aktuellen Zustand ab. Diese Zustandsänderung wird als Übergang bezeichnet.
Der Betrieb der Maschine kann mathematisch durch eine Übergangsfunktion der Form d(Scurrent, x) = Snew beschrieben werden. Ansonsten kann man es wie folgt schreiben:
d(gerade, 0) = gerade. d(gerade, 1) = ungerade.
d(ungerade, 0) = ungerade. d(ungerade, 1) = gerade.
Der Controller hat einen einzigen akzeptierenden Zustand, ODD, und EVEN ist ein „ablehnender“ Zustand. Lassen Sie uns die Abfolge der Übergänge der Maschine widerspiegeln, wenn die Kette 1101 an ihren Eingang angelegt wird.
GERADE ® UNGERADE ® GERADE ® GERADE ® UNGERADE
Die Übergangstabelle eines solchen Automaten hat die Form:
| sogar | sogar | seltsam |
| seltsam | seltsam | sogar |
Definition. Ein endlicher Automat ist ein formales System
S = ( A, Q, d, l, V ),
deren Objekte die folgenden sind:
* A ist eine endliche Menge von Eingabesymbolen (Menge
Terminals);
* Q – endliche Menge interner Zustände des Automaten
(Satz von Nichtterminals);
* V – endliche Menge von Ausgabesymbolen (Ausgabealphabet);
* d - Übergangsfunktion, die durch A ´ Q ® Q gekennzeichnet ist;
* l – Ausgabefunktion, die die Anzeige der Ansicht bestimmt.
In diesem Artikel bezieht sich der Begriff „Finite-State-Machine“ auf einen Algorithmus, der sich in einem von wenigen Zuständen befinden kann. „Zustand“ ist eine bestimmte Bedingung, die eine bestimmte Beziehung zwischen Eingangs- und Ausgangssignalen sowie Eingangssignalen und nachfolgenden Zuständen definiert. Ein intelligenter Leser wird sofort bemerken, dass es sich bei den in diesem Artikel beschriebenen Finite-State-Maschinen um Mealy-Maschinen handelt. Eine Mealy-Maschine ist eine endliche Zustandsmaschine, deren Ausgänge Funktionen des aktuellen Zustands und des Eingangssignals sind, im Gegensatz zu einer Moore-Maschine, bei der die Ausgänge nur Funktionen des Zustands sind. In beiden Fällen ist der Folgezustand eine Funktion des aktuellen Zustands und des Eingangssignals.
Schauen wir uns ein Beispiel einer einfachen endlichen Zustandsmaschine an. Stellen Sie sich vor, dass Sie in einer Textzeichenfolge die Zeichenfolge „//“ erkennen müssen. Abbildung 1 zeigt, wie dies mithilfe einer Zustandsmaschine geschieht. Das erste Auftreten eines Schrägstrichs erzeugt kein Ausgangssignal, sondern führt dazu, dass die Maschine in den zweiten Zustand übergeht. Wenn die Maschine im zweiten Zustand keinen Schrägstrich findet, kehrt sie zum ersten zurück, da hierfür zwei Schrägstriche hintereinander erforderlich sind. Wird der zweite Schrägstrich gefunden, gibt die Maschine ein „Bereit“-Signal aus.
Finden Sie heraus, was der Kunde braucht.
Erstellen Sie ein Zustandsübergangsdiagramm
Codieren Sie das „Skelett“ einer Zustandsmaschine, ohne die Verzweigungsoperationen im Detail zu beschreiben.
Stellen Sie sicher, dass die Übergänge ordnungsgemäß funktionieren.
Seien Sie bei den Übergangsdetails genau.
Nimm den Test.
Beispiel für einen Zustandsautomaten
Schauen wir uns ein interessanteres Beispiel einer Zustandsmaschine an – ein Programm, das das Ein- und Ausfahren des Fahrwerks eines Flugzeugs steuert. Obwohl die meisten Flugzeuge diesen Vorgang über eine elektrohydraulische Steuerung durchführen (einfach weil kein Computer an Bord ist), lohnt es sich in manchen Fällen, beispielsweise bei unbemannten Luftfahrzeugen, auf eine Softwaresteuerung zurückzugreifen.
Schauen wir uns zunächst die Ausstattung an. Das Fahrwerk des Flugzeugs besteht aus einem Bugfahrwerk, einem linken Hauptfahrwerk und einem rechten Hauptfahrwerk. Sie werden durch einen hydraulischen Mechanismus angetrieben. Eine elektrisch angetriebene Hydraulikpumpe versorgt den Kraftaktuator mit Druck. Mittels Software Die Pumpe schaltet sich ein oder aus. Der Computer passt die Position des Richtungsventils – „nach unten“ oder „nach oben“ – an, um Druck zum Anheben oder Absenken des Fahrwerks zu ermöglichen. Jede der Fahrgestellstützen verfügt über einen Endschalter: Eine davon schließt, wenn das Fahrgestell angehoben wird, die andere, wenn es in der unteren Position verriegelt ist. Um festzustellen, ob das Flugzeug am Boden ist, schließt ein Endschalter an der Bugfahrwerksstrebe, wenn das Gewicht des Flugzeugs auf dem Bugfahrwerk lastet. Die Bedienelemente des Piloten bestehen aus einem oberen/unteren Fahrwerksarm und drei Lichtern (eines für jedes Bein), die ausgeschaltet werden können, grün (untere Position) oder rot (Startposition).
Kommen wir nun zur Entwicklung einer endlichen Zustandsmaschine. Der erste und schwierigste Schritt besteht darin, die tatsächlichen Erwartungen des Kunden zu verstehen. Einer der Vorteile einer endlichen Zustandsmaschine besteht darin, dass sie den Programmierer dazu zwingt, alle möglichen Fälle durchzudenken und dadurch alle erforderlichen Informationen vom Kunden zu erhalten. Warum halte ich dies für die schwierigste Phase? Und wie oft wurde Ihnen schon eine ähnliche Aufgabenbeschreibung gegeben: Fahren Sie das Fahrwerk nicht ein, wenn das Flugzeug am Boden steht.
Das ist natürlich wichtig, aber der Kunde glaubt, dass hier alles endet. Was ist mit den restlichen Fällen? Reicht es aus, das Fahrwerk einzufahren, sobald das Flugzeug vom Boden abhebt? Was passiert, wenn das Flugzeug auf einer Unebenheit auf der Landebahn abprallt? Was passiert, wenn der Pilot beim Parken den Schaltknüppel in die obere Position bewegt und dadurch mit dem Abheben beginnt? Sollte in diesem Fall das Fahrwerk angehoben werden?
Einer der Vorteile des Denkens in Form einer Zustandsmaschine besteht darin, dass Sie schnell ein Zustandsübergangsdiagramm auf einer Projektionstafel direkt vor den Augen des Kunden zeichnen und den gesamten Prozess gemeinsam mit ihm durchlaufen können. Als Bezeichnung für den Zustandsübergang wird akzeptiert: „das Ereignis, das den Übergang verursacht hat“/„das Ausgangssignal als Ergebnis des Übergangs“. Hätten wir nur das entwickelt, was der Kunde ursprünglich verlangte („Fahrwerk nicht einfahren, wenn das Flugzeug am Boden steht“), dann hätten wir die in Abbildung 2 gezeigte Maschine erhalten.
Beachten Sie beim Erstellen eines Zustandsübergangsdiagramms (oder eines anderen Algorithmus) Folgendes:
Computer arbeiten im Vergleich zu mechanischen Geräten sehr schnell
Der Maschinenbauingenieur, der erklärt, was zu tun ist, weiß möglicherweise nicht so viel über Computer und Algorithmen wie Sie. Und das auch positiver Punkt, sonst würde man dich nicht brauchen!
Wie verhält sich Ihr Programm, wenn ein mechanisches oder elektrisches Teil kaputt geht?
Eine Zustandsmaschine basierend auf den tatsächlichen Kundenanforderungen ist in Abbildung 3 dargestellt. Hier wollen wir verhindern, dass das Fahrwerk des Flugzeugs einfährt, bis es definitiv in der Luft ist. Dazu wartet die Maschine nach dem Öffnen des Etagenschalters einige Sekunden. Wir möchten auch auf die steigende Kante des Hebels des Piloten und nicht auf die Höhe reagieren, um Probleme zu vermeiden, wenn jemand den Hebel bewegt, während sich das Flugzeug im Park befindet. Das Ein- bzw. Ausfahren des Fahrwerks dauert einige Sekunden und wir müssen damit rechnen, dass der Pilot während dieses Vorgangs seine Meinung ändert und den Hebel in die entgegengesetzte Richtung bewegt. Beachten Sie außerdem, dass, wenn das Flugzeug erneut landet, während wir uns im Status „Warten auf den Start“ befinden, der Timer neu startet und das Fahrwerk nur dann eingefahren wird, wenn das Flugzeug 2 Sekunden in der Luft ist.
Implementierung einer endlichen Zustandsmaschine
Listing 1 ist meine Implementierung der in Abbildung 3 gezeigten Zustandsmaschine. Lassen Sie uns einige Details des Codes besprechen.
/*Auflistung 1*/
typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) State_Type;
/*Dieses Array enthält Zeiger auf Funktionen, die in bestimmten Zuständen aufgerufen werden*/
Leere(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);
State_Type curr_state;
InitializeLdgGearSM();
/*Das Herzstück der Maschine ist diese Endlosschleife. Funktion entsprechend
Aktueller Status, einmal pro Iteration aufgerufen */
während (1) {
state_table();
DecrementTimer();
Leere InitializeLdgGearSM( Leere )
curr_state = GEAR_DOWN;
/*Geräte anhalten, Lichter ausschalten usw.*/
Leere Herunterschalten( Leere )
/* Gehe in den Wartezustand, wenn das Flugzeug
Nicht am Boden und erhielt den Befehl, das Fahrwerk anzuheben*/
Wenn((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) (
curr_state = WTG_FOR_TKOFF;
prev_gear_lever = gear_lever;
Leere RaisingGear( Leere )
Wenn((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (
curr_state = GEAR_UP;
/*Wenn der Pilot seine Entscheidung geändert hat, gehe in den Zustand „Fahrwerk senken“*/
Wenn(gear_lever == DOWN) (
curr_state = LOWERING_GEAR;
Leere Aufrüsten( Leere )
/*wenn der Pilot den Hebel in die „unten“-Position bewegt hat,
Wir gehen in den Zustand „Fahrwerksabsenkung“*/
Wenn(gear_lever == DOWN) (
curr_state = LOWERING_GEAR;
Leere WtgForTakeoff( Leere )
/* Warten Sie, bevor Sie das Fahrwerk anheben.*/
Wenn(Timer<= 0.0) {
curr_state = RAISING_GEAR;
/*Wenn wir uns erneut berühren oder der Pilot seine Meinung ändert, fangen Sie noch einmal von vorne an*/
Wenn((squat_switch == DOWN) || (gear_lever == DOWN)) (
curr_state = GEAR_DOWN;
/* Ich möchte nicht verlangen, dass er den Hebel erneut umlegt
Das war nur ein Sprung.*/
prev_gear_lever = DOWN;
Leere LoweringGear( Leere )
Wenn(gear_lever == UP) (
curr_state = RAISING_GEAR;
Wenn((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (
curr_state = GEAR_DOWN;
Zunächst fällt Ihnen vielleicht auf, dass die Funktionalität jedes Zustands durch eine separate C-Funktion implementiert wird. Natürlich wäre es möglich, einen Automaten mithilfe einer Switch-Anweisung mit einem separaten Fall für jeden Zustand zu implementieren, aber dies kann zu einer sehr langen Funktion führen (10–20 Codezeilen pro Zustand für jeden der 20–30 Zustände). . Dies kann auch zu Fehlern führen, wenn Sie den Code in der letzten Testphase ändern. Sie haben vielleicht noch nie eine Break-Anweisung am Ende eines Falles vergessen, aber solche Fälle sind mir passiert. Der Code für einen Staat wird nie im Code für einen anderen landen, wenn Sie für jeden Staat eine eigene Funktion haben.
Um die Verwendung einer Switch-Anweisung zu vermeiden, verwende ich ein Array von Zeigern auf Zustandsfunktionen und deklariere die als Index des Arrays verwendete Variable als Typ Enum.
Der Einfachheit halber wird die E/A-Hardware, die für das Lesen des Zustands von Schaltern, das Ein- und Ausschalten von Pumpen usw. verantwortlich ist, als einfache Variablen dargestellt. Es wird angenommen, dass es sich bei diesen Variablen um „magische Adressen“ handelt, die auf unsichtbare Weise mit der Hardware verknüpft sind.
Die andere offensichtliche Sache ist, dass Code an dieser Stelle keine wirkliche Rolle spielt. Er bewegt sich einfach von einem Staat in einen anderen. Dies ist ein wichtiger Zwischenschritt und sollte nicht ignoriert werden. Übrigens wäre es schön, Druckanweisungen zwischen Anweisungen zur bedingten Kompilierung (#ifdef DEBUG .. #endif) einzufügen, die den aktuellen Status und die Werte der Eingangssignale drucken würden.
Der Schlüssel zum Erfolg liegt im Code, der den Zustandsübergang bewirkt, d. h. stellt fest, dass eine Dateneingabe stattgefunden hat.
Wenn der Code alle Zustände korrekt durchläuft, besteht der nächste Schritt darin, die „Füllung“ des Codes zu schreiben, also genau das, was das Ausgangssignal erzeugt. Denken Sie daran, dass jeder Übergang ein Eingangssignal (das Ereignis, das ihn verursacht hat) und ein Ausgangssignal (das Hardware-I/O-Gerät, wie in unserem Beispiel) hat. Oft ist es sinnvoll, dies in Form einer Zustandsübergangstabelle zu erfassen.
In der Zustandsübergangstabelle gibt es eine Zeile pro Zustandsübergang.
Versuchen Sie beim Codieren eines Zustandsautomaten, seine Stärke zu bewahren – eine klare Übereinstimmung zwischen den Anforderungen des Kunden und dem Code. Es kann erforderlich sein, Hardwaredetails in einer anderen Funktionsschicht auszublenden, um beispielsweise den Code der Zustandsmaschine so ähnlich wie eine Zustandsübergangstabelle und ein Zustandsübergangsdiagramm aussehen zu lassen. Diese Symmetrie hilft, Fehler zu vermeiden und erklärt, warum Zustandsmaschinen ein so wichtiger Teil des Arsenals eines Programmierers für eingebettete Systeme sind. Den gleichen Effekt könnte man natürlich auch mit Checkboxen und unendlich vielen verschachtelten if-Anweisungen erzielen, aber das würde es sehr schwierig machen, den Code nachzuvollziehen und ihn mit den Wünschen des Kunden zu vergleichen.
Der Codeausschnitt in Listing 2 erweitert die Funktion RaisingGear(). Beachten Sie, dass der Code für die Funktion RaisingGear() darauf abzielt, die beiden Zeilen der Übergangstabelle für den Status „Raising Gear“ zu spiegeln.
Leere RaisingGear( Leere )
/*Nachdem alle Schalter angehoben sind, gehen wir in den Zustand „Chassis angehoben“*/
Wenn((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (
pump_motor = AUS;
gear_lights = LÖSCHEN;
curr_state = GEAR_UP;
/*Wenn der Pilot seine Meinung ändert, beginnen Sie mit dem Einfahren des Fahrwerks*/
Wenn(gear_lever == DOWN) (
pump_direction = DOWN;
curr_state = GEAR_LOWERING;
Denken Sie daran, latente Zustände zu vermeiden. Ein versteckter Zustand entsteht, wenn Sie aus Faulheit versuchen, einen bedingten Unterzustand hinzuzufügen, anstatt einen bestimmten Zustand hinzuzufügen. Wenn Ihr Code beispielsweise dasselbe Eingangssignal je nach Modus auf unterschiedliche Weise verarbeitet (d. h. unterschiedliche Zustandsübergänge auslöst), handelt es sich um einen verborgenen Zustand. In diesem Fall würde ich mich fragen, ob dieser Staat in zwei Teile geteilt werden sollte? Durch die Verwendung versteckter Zustände wird der Vorteil der Verwendung einer Zustandsmaschine zunichte gemacht.
Als Übung können Sie die Zustandsmaschine, die wir gerade betrachtet haben, erweitern, indem Sie eine Zeitüberschreitung zum Zyklus zum Ein- oder Ausfahren des Fahrwerks hinzufügen, weil ... Der Maschinenbauer möchte nicht, dass die Hydraulikpumpe länger als 60 Sekunden läuft. Wenn der Zyklus endet, muss der Pilot durch ein Umschalten zwischen grünem und rotem Licht gewarnt werden und in der Lage sein, den Hebel erneut zu bewegen, um es erneut zu versuchen. Vielleicht möchten Sie auch einen hypothetischen Maschinenbauingenieur fragen, welche Auswirkungen die Umkehr der Laufrichtung einer Pumpe während des Betriebs auf die Pumpe hat, da dies in zwei Fällen geschieht, wenn der Pilot seine Meinung ändert. Natürlich wird der Mechaniker sagen, dass es negativ ist. Wie würden Sie dann die Zustandsmaschine modifizieren, um die Pumpe bei einem Richtungswechsel schnell anzuhalten?
Zustandsmaschinentests
Das Schöne an der Codierung von Algorithmen als Zustandsmaschinen ist, dass sich der Testplan fast automatisch selbst schreibt. Sie müssen lediglich jeden Zustandsübergang durchlaufen. Normalerweise mache ich das mit einem Marker in der Hand und streiche die Pfeile im Zustandsübergangsdiagramm durch, wenn sie den Test bestehen. Dies ist eine gute Möglichkeit, „verborgene Zustände“ zu vermeiden – sie werden in Tests häufiger übersehen als bestimmte Zustände.
Dies erfordert viel Geduld und viel Kaffee, da selbst eine mittelgroße Zustandsmaschine bis zu 100 verschiedene Übergänge haben kann. Die Anzahl der Übergänge ist übrigens eine gute Möglichkeit, die Komplexität eines Systems zu messen. Letzteres wird durch die Anforderungen des Kunden bestimmt und der Zustandsautomat macht den Prüfumfang ersichtlich. Bei einem weniger organisierten Ansatz kann der Umfang der erforderlichen Tests genauso beeindruckend sein, aber Sie werden es einfach nicht bemerken.
Es ist sehr praktisch, in Ihrem Code Druckanweisungen zu verwenden, die den aktuellen Status und die Werte von Ein- und Ausgangssignalen anzeigen. Auf diese Weise können Sie leicht beobachten, was die Goldene Regel des Softwaretests ausdrückt: Überprüfen Sie, ob das Programm das tut, was es tun soll, und auch, dass es nichts Unnötiges tut. Mit anderen Worten: Erhalten Sie nur die Ergebnisse, die Sie erwarten, und was geschieht darüber hinaus noch? Gibt es „schwierige“ Zustandsübergänge, d.h. Gibt an, dass zufällig nur eine Wiederholung der Schleife durchlaufen wird? Ändern sich die Ausgaben, wenn Sie dies nicht erwarten? Im Idealfall sollte die Ausgabe Ihres printfs deutlich einer Zustandsübergangstabelle ähneln.
Abschließend – und das gilt für jede eingebettete Software, nicht nur für State-Machine-basierte Software – seien Sie sehr vorsichtig, wenn Sie die Software zum ersten Mal auf echter Hardware ausführen. Es ist sehr leicht, die Signalpolarität falsch zu verstehen – „Oh, ich dachte, 1 bedeutet Fahrwerk ausgefahren und 0 bedeutet Fahrwerk ausgefahren.“ In vielen Fällen nutzte mein Hardware-Assistent einen temporären „Chicken Switch“, um wertvolle Komponenten zu schützen, bis er sicher war, dass meine Software die Dinge in die richtige Richtung bewegte.
Start
Wenn alle Anforderungen des Kunden erfüllt sind, kann ich in ein paar Tagen eine Zustandsmaschine ähnlicher Komplexität starten. Fast immer machen die Maschinen, was ich will. Am schwierigsten ist es natürlich, die Wünsche des Kunden genau zu verstehen und sicherzustellen, dass der Kunde selbst weiß, was er will. Letzteres dauert viel länger!
Martin Gomez ist Programmierer am Applied Physics Laboratory der Johns Hopkins University. Beteiligt sich an der Softwareentwicklung zur Unterstützung von Flügen von Forschungsraumfahrzeugen. 17 Jahre lang im Bereich der Entwicklung eingebetteter Systeme tätig. Martin hat einen Bachelor of Science in Luft- und Raumfahrttechnik und einen Master of Science in Elektrotechnik von der Cornell University.
Endliche Maschine: Theorie und Implementierung
Eine endliche Zustandsmaschine ist ein abstraktes Modell, das eine endliche Anzahl von Zuständen von etwas enthält. Wird zur Darstellung und Steuerung des Ausführungsflusses beliebiger Befehle verwendet. Die Zustandsmaschine eignet sich ideal für die Implementierung künstlicher Intelligenz in Spielen und liefert eine übersichtliche Lösung, ohne sperrigen und komplexen Code schreiben zu müssen. In diesem Artikel werden wir uns mit der Theorie befassen und auch lernen, wie man eine einfache und stapelbasierte Zustandsmaschine verwendet.
Wir haben bereits eine Reihe von Artikeln zum Schreiben künstlicher Intelligenz mithilfe einer endlichen Zustandsmaschine veröffentlicht. Wenn Sie diese Serie noch nicht gelesen haben, können Sie dies jetzt nachholen:
Was ist eine endliche Zustandsmaschine?
Eine Finite-State-Maschine (oder einfach FSM – Finite-State-Machine) ist ein Rechenmodell, das auf einer hypothetischen Zustandsmaschine basiert. Es kann jeweils nur ein Zustand aktiv sein. Daher muss die Maschine ihren Zustand ändern, um Aktionen ausführen zu können.
Zustandsmaschinen werden typischerweise verwendet, um den Ausführungsfluss von etwas zu organisieren und darzustellen. Dies ist besonders nützlich, wenn KI in Spielen implementiert wird. Um zum Beispiel das „Gehirn“ eines Feindes zu schreiben: Jeder Zustand repräsentiert eine Art Aktion (Angriff, Ausweichen usw.).
Ein endlicher Automat kann als Graph dargestellt werden, dessen Scheitelpunkte Zustände und dessen Kanten Übergänge zwischen ihnen sind. Jede Kante verfügt über eine Beschriftung, die angibt, wann der Übergang erfolgen soll. Im Bild oben können Sie beispielsweise sehen, dass die Maschine den Zustand „Wandern“ in den Zustand „Angriff“ ändert, sofern sich der Spieler in der Nähe befindet.
Planungszustände und ihre Übergänge
Die Implementierung eines endlichen Automaten beginnt mit der Identifizierung seiner Zustände und Übergänge zwischen ihnen. Stellen Sie sich eine Zustandsmaschine vor, die die Aktionen einer Ameise beschreibt, die Blätter zu einem Ameisenhaufen trägt:
Ausgangspunkt ist der Zustand „Blatt finden“, der solange aktiv bleibt, bis die Ameise das Blatt findet. Wenn dies geschieht, ändert sich der Zustand in „nach Hause gehen“. Derselbe Zustand bleibt aktiv, bis unsere Ameise den Ameisenhaufen erreicht. Danach ändert sich der Zustand wieder auf „Blatt finden“.
Wenn der Status „Blatt finden“ aktiv ist, sich der Mauszeiger jedoch in der Nähe der Ameise befindet, ändert sich der Status in „Weglaufen“. Sobald die Ameise einen ausreichend sicheren Abstand zum Mauszeiger hat, ändert sich der Status wieder in „Blatt finden“.
Bitte beachten Sie, dass die Ameise beim Heim- oder Weggehen keine Angst vor dem Mauszeiger hat. Warum? Sondern weil es keinen entsprechenden Übergang gibt.
Implementierung eines einfachen endlichen Automaten
Ein endlicher Automat kann mit einer einzigen Klasse implementiert werden. Nennen wir es FSM. Die Idee besteht darin, jeden Zustand als Methode oder Funktion zu implementieren. Wir werden auch die Eigenschaft activeState verwenden, um den aktiven Zustand zu bestimmen.
Öffentliche Klasse FSM ( private var activeState:Function; // Zeiger auf den aktiven Zustand der Maschine öffentliche Funktion FSM() ( ) öffentliche Funktion setState(state:Function) :void ( activeState = state; ) öffentliche Funktion update() :void ( if ( activeState != null) ( activeState(); ) ) )
Jeder Zustand ist eine Funktion. Darüber hinaus wird es jedes Mal aufgerufen, wenn der Spielrahmen aktualisiert wird. Wie bereits erwähnt, speichert activeState einen Zeiger auf die aktive Statusfunktion.
Die update()-Methode der FSM-Klasse muss in jedem Frame des Spiels aufgerufen werden. Und es ruft wiederum die Funktion des aktuell aktiven Zustands auf.
Die Methode setState() legt den neuen aktiven Zustand fest. Darüber hinaus gehört nicht jede Funktion, die einen bestimmten Zustand des Automaten definiert, unbedingt zur FSM-Klasse – das macht unsere Klasse universeller.
Verwendung einer Zustandsmaschine
Lassen Sie uns eine Ameisen-KI implementieren. Oben haben wir bereits eine Reihe seiner Zustände und Übergänge zwischen ihnen gezeigt. Lassen Sie uns sie noch einmal veranschaulichen, aber dieses Mal konzentrieren wir uns auf den Code.
Unsere Ameise wird durch die Ameisenklasse repräsentiert, die über ein Gehirnfeld verfügt. Dies ist nur eine Instanz der FSM-Klasse.
Öffentliche Klasse Ant ( öffentliche Variable Position:Vector3D; öffentliche Variable Geschwindigkeit:Vector3D; öffentliche Variable Brain:FSM; öffentliche Funktion Ant(posX:Number, posY:Nummer) ( Position = neues Vector3D(posX, posY); Geschwindigkeit = neues Vector3D( -1, -1); brain = new FSM(); * Lässt die Ameise nach Blättern suchen. . * Lässt die Ameise zum Ameisenhaufen gehen */ public function goHome() :void ( ) /** * State „runAway“. / public function runAway() :void ( ) public function update():void ( // Update die Zustandsmaschine. Diese Funktion ruft die // aktive Zustandsfunktion auf: moveBasedOnVelocity();
Die Ant-Klasse enthält auch Geschwindigkeits- und Positionseigenschaften. Diese Variablen werden zur Berechnung der Bewegung mithilfe der Euler-Methode verwendet. Die Funktion update() wird jedes Mal aufgerufen, wenn der Spielrahmen aktualisiert wird.
Nachfolgend finden Sie eine Implementierung jeder Methode, beginnend mit findLeaf() – dem Zustand, der für das Finden von Blättern verantwortlich ist.
Öffentliche Funktion findLeaf() :void ( // Bewegt die Ameise zum Blatt. Velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance (Spiel .instance.leaf, dies)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }
goHome()-Status – wird verwendet, um die Ameise nach Hause zu bringen.
Öffentliche Funktion goHome() :void ( // Bewegt die Ameise zum Haus speed = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( Spiel. Instanz.home, dies)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }
Und schließlich wird der Zustand runAway() verwendet, wenn man dem Mauszeiger ausweicht.
Öffentliche Funktion runAway() :void ( // Bewegt die Ameise vom Cursor weg Velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Ist der Cursor noch in der Nähe? ? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Nein, es ist schon weit weg. Es ist Zeit, wieder nach dem Blatt zu suchen. brain.setState(findLeaf); ) )
FSM-Verbesserung: Stapelbasierter Automat
Stellen Sie sich vor, dass eine Ameise auf dem Heimweg ebenfalls vor dem Mauszeiger davonlaufen muss. So werden die FSM-Staaten aussehen:
Es scheint eine triviale Änderung zu sein. Nein, diese Änderung stellt für uns ein Problem dar. Stellen Sie sich vor, der aktuelle Zustand sei „weggelaufen“. Was soll der Mauszeiger tun, wenn er sich von der Ameise wegbewegt: nach Hause gehen oder nach einem Blatt suchen?
Die Lösung für dieses Problem ist eine stapelbasierte Zustandsmaschine. Im Gegensatz zum einfachen FSM, den wir oben implementiert haben, verwendet dieser FSM-Typ einen Stapel, um Zustände zu verwalten. An der Spitze des Stapels befindet sich der aktive Zustand, und Übergänge treten auf, wenn Zustände zum Stapel hinzugefügt bzw. daraus entfernt werden.
Und hier ist eine visuelle Demonstration der Funktionsweise einer stapelbasierten Zustandsmaschine:
Implementierung eines Stack-basierten FSM
Eine solche Zustandsmaschine kann auf die gleiche Weise wie eine einfache implementiert werden. Der Unterschied besteht in der Verwendung eines Arrays von Zeigern auf die erforderlichen Zustände. Wir benötigen die Eigenschaft activeState nicht mehr, weil Die Oberseite des Stapels zeigt bereits auf den aktiven Zustand.
Öffentliche Klasse StackFSM ( private var stack:Array; öffentliche Funktion StackFSM() ( this.stack = new Array(); ) öffentliche Funktion update() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) öffentliche Funktion popState() :Function ( return stack.pop(); ) public function pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ; ) ) öffentliche Funktion getCurrentState() :Function ( return stack.length > 0 ? stack : null; ) )
Beachten Sie, dass die Methode setState() durch pushState() (Hinzufügen eines neuen Zustands oben im Stapel) und popState() (Entfernen eines Zustands oben im Stapel) ersetzt wurde.
Verwendung von stapelbasiertem FSM
Es ist wichtig zu beachten, dass bei Verwendung einer stapelbasierten Zustandsmaschine jeder Zustand dafür verantwortlich ist, vom Stapel entfernt zu werden, wenn er nicht mehr benötigt wird. Beispielsweise sollte sich der Zustand attack() vom Stapel entfernen, wenn der Feind bereits zerstört wurde.
Öffentliche Klasse Ant ( (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Beginnen Sie mit der Suche nach dem Blatthirn. pushState( findLeaf); (...) ) /** * State „findLeaf“. * Zwingt die Ameise, nach Blättern zu suchen */ public function findLeaf() :void ( // Bewegt die Ameise zum Blatt. Velocity = new Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // Nein, es ist schon weit weg. Es ist Zeit, wieder nach Blättern zu suchen. brain.popState(); ) ) (...) )
Abschluss
Zustandsmaschinen sind sicherlich nützlich für die Implementierung der Logik künstlicher Intelligenz in Spielen. Sie können einfach als Diagramm dargestellt werden, sodass der Entwickler alle möglichen Optionen sehen kann.
Die Implementierung einer Zustandsmaschine mit Zustandsfunktionen ist eine einfache, aber leistungsstarke Technik. Noch komplexere Zustandsverflechtungen können mit FSM implementiert werden.
Das Ergebnis des Betriebs der Maschine wird durch ihren Endzustand bestimmt.
Es gibt verschiedene Möglichkeiten, einen endlichen Automaten zu spezifizieren. Beispielsweise kann eine Zustandsmaschine mit fünf Parametern angegeben werden: , wobei:
Die Maschine beginnt im Zustand q 0 zu arbeiten und liest jeweils ein Zeichen aus der Eingabezeichenfolge. Das gelesene Symbol überführt die Maschine gemäß der Übergangsfunktion in einen neuen Zustand von Q. Befindet sich die Maschine nach Abschluss des Lesens des Eingabeworts (Symbolkette) in einem der Akzeptanzzustände, wird das Wort von der Maschine „akzeptiert“. In diesem Fall soll es zur Sprache des gegebenen Automaten gehören. Andernfalls lautet das Wort „abgelehnt“.
Zustandsmaschinen werden in der Praxis häufig verwendet, beispielsweise in Parsern, lexikalischen Analysatoren und modellbasierten Softwaretests.
Andere Arten der Beschreibung
- Zustandsdiagramm ( oder manchmal Übergangsdiagramm) – grafische Darstellung einer Reihe von Zuständen und Übergangsfunktionen. Es handelt sich um einen geladenen unidirektionalen Graphen, dessen Scheitelpunkte die Zustände des Raumfahrzeugs sind, dessen Kanten Übergänge von einem Zustand in einen anderen sind und die Symbole, an denen dieser Übergang auftritt. Wenn der Übergang vom Zustand q1 zum Zustand q2 durchgeführt werden kann, erfolgt das Erscheinen eines von mehrere Symbole, dann müssen sie alle über dem Bogen des Diagramms (Zweig des Diagramms) eingeschrieben werden.
- Übergangstabelle- tabellarische Darstellung der Funktion δ. Typischerweise entspricht in einer solchen Tabelle jede Zeile einem Zustand und jede Spalte einem gültigen Eingabesymbol. In die Zelle am Schnittpunkt von Zeile und Spalte wird die Aktion geschrieben, die die Maschine ausführen muss, wenn sie in einer Situation, in der sie sich in einem bestimmten Zustand befand, am Eingang ein bestimmtes Symbol empfangen hat.
Determinismus
Endliche Maschinen werden in deterministische und nichtdeterministische Maschinen unterteilt.
Deterministische endliche Zustandsmaschine
- Ein deterministischer endlicher Automat (DFA) ist ein Automat, bei dem es für jede Folge von Eingabesymbolen nur einen Zustand gibt, in den der Automat vom aktuellen Zustand aus wechseln kann.
- Ein nichtdeterministischer endlicher Automat (NFA) ist eine Verallgemeinerung eines deterministischen Automaten. Der Nichtdeterminismus von Automaten wird auf zwei Arten erreicht:
| Es gibt Übergänge, die mit einer Leerkette ε gekennzeichnet sind | Aus einem Zustand gehen mehrere Übergänge hervor, die mit demselben Symbol gekennzeichnet sind |
|---|---|
Betrachten wir den Fall, dass die Maschine wie folgt spezifiziert ist: , wobei:
Dann erscheint das dritte Zeichen des Nichtdeterminismus – das Vorhandensein mehrerer Anfangszustände (Startzustände) des Automaten.
Es gibt einen Satz, der besagt: „Jeder nichtdeterministische endliche Automat kann in einen deterministischen umgewandelt werden, sodass seine Sprachen übereinstimmen“ (solche Automaten werden als äquivalent bezeichnet). Da jedoch die Anzahl der Staaten in einem äquivalenten DFA im schlimmsten Fall exponentiell mit der Anzahl der Staaten des ursprünglichen DFA wächst, ist eine solche Bestimmung in der Praxis nicht immer möglich. Darüber hinaus sind endliche Automaten mit Ausgängen im Allgemeinen nicht bestimmbar.
Aufgrund der letzten beiden Bemerkungen werden NFAs trotz der größeren Komplexität nichtdeterministischer endlicher Automaten überwiegend für Aufgaben im Zusammenhang mit der Textverarbeitung verwendet.
Automaten und reguläre Sprachen
Für einen Automaten kann man eine Sprache (eine Menge von Wörtern) im Alphabet Σ definieren, das er ist Ist- Dies sind die Namen von Wörtern. Bei der Eingabe wechselt die Maschine vom Anfangszustand in einen der Zustände der Menge F.
Spezialisierte Programmiersprachen
- Die SFC-Sprache (Sequential Function Chart) ist eine grafische Programmiersprache, die häufig zur Programmierung industrieller Logiksteuerungen (SPS) verwendet wird.
In SFC wird ein Programm als schematische Abfolge von Schritten beschrieben, die durch Transitionen verbunden sind.
Modellentwicklung mit endlichen Automaten
Endliche Maschinen ermöglichen die Erstellung von Modellen paralleler Verarbeitungssysteme. Um jedoch die Anzahl paralleler Prozesse in einem solchen Modell zu ändern, müssen erhebliche Änderungen am Modell selbst vorgenommen werden. Darüber hinaus führt der Versuch, ein komplexes Modell auf einer endlichen Zustandsmaschine zu entwickeln, zu einem schnellen Anstieg der Anzahl der Zustände der Maschine, was die Entwicklung eines solchen Modells letztendlich zu einer äußerst mühsamen Aufgabe macht. Wie oben erwähnt, kann das letzte Problem durch die Verwendung eines nichtdeterministischen Automaten gelöst werden.
Anmerkungen
siehe auch
- Sequentielle Logik (Sequentielle Logik)
Links
- Automatentheorie / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Wahrscheinlichkeitstheorie. Mathe-Statistik. Theoretische Kybernetik. - M.: VINITI, 1976. - T. 13. - S. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
- Anwendung endlicher Automaten zur Lösung von Automatisierungsproblemen
- Ein Beispiel für eine Finite-State-Machine-Implementierung in Python für das Django-Framework
Wikimedia-Stiftung. 2010.
- Keynes, John Maynard
- Zustandsdiagramm (Automatentheorie)
Sehen Sie in anderen Wörterbüchern, was eine „Finite State Machine“ ist:
Zustandsmaschine- CA-Rechenmodell, das einen Automaten mit einer endlichen Anzahl von Zuständen beschreibt. CAs werden häufig in der Programmierung verwendet, beispielsweise in lexikalischen Analysatoren von Compilern. Finite-State-Machine Sequenzspezifikation... ...
Zustandsmaschine- mathematisches Modell eines Geräts mit endlichem Speicher. Eine Zustandsmaschine verarbeitet mehrere diskrete Eingangssignale in mehrere Ausgangssignale. Es gibt synchrone und asynchrone Finite-State-Maschinen. Auf Englisch: Finite-State-Maschine Siehe... Finanzwörterbuch
Zustandsmaschine- baigtinis automatas statusas T sritis automatika atitikmenys: engl. endlicher Automat; Finite-State-Machine-Vok. endlicher Automat, m; Finalautomat, m rus. endliche Zustandsmaschine, m pranc. final automatisieren, m; fini, m automatisieren; automate terminal, m;… … Automatikos terminų žodynas
FINITE-STATE-MASCHINE- ein Automat, der viele Zustände sowie viele Ein- und Ausgangssignale hat, sind endlich. K. a. Möglicherweise handelt es sich um ein technisches Modell. Geräte (Computer, Relaisgerät) oder biol. Systeme (idealisiertes tierisches Nervensystem). Wichtig... ... Großes enzyklopädisches polytechnisches Wörterbuch
modulare Zustandsmaschine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Englisch-Russisches Wörterbuch der Elektrotechnik und Energietechnik, Moskau, 1999] Themen der Elektrotechnik, Grundkonzepte EN endlicher modularer Automat ... Leitfaden für technische Übersetzer
Verfügbarkeitszustandsmaschine- (ITU T Y.1711). Themen: Telekommunikation, Grundkonzepte EN Verfügbarkeit ZustandsmaschineASM... Leitfaden für technische Übersetzer
Zustandsmaschine mit Speicher- Ein endlicher Automat mit Speicher ist ein mathematisches Modell eines Geräts, dessen Verhalten sowohl von den Eingabebedingungen als auch vom vorherigen Zustand abhängt. Um einen endlichen Automaten mit Gedächtnis zu beschreiben, werden die Sprachen Operatorschemata, reguläre... ... Wikipedia verwendet
deterministische endliche Zustandsmaschine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Englisch-Russisches Wörterbuch der Elektrotechnik und Energietechnik, Moskau, 1999] Themen der Elektrotechnik, Grundkonzepte EN endlicher deterministischer Automat ... Leitfaden für technische Übersetzer
Moore-Maschine- (Automat zweiter Art) in der Berechnungstheorie ein endlicher Automat, dessen Ausgangswert des Signals nur vom aktuellen Zustand des gegebenen Automaten abhängt und im Gegensatz zum Mealy-Automaten nicht direkt von diesem abhängt Eingabewerte. Moores Automat heißt... Wikipedia
Eine Sprache in einem Alphabet ist eine beliebige Menge von Wörtern in diesem Alphabet. Eine Sprache, die alle Wörter des Alphabets (einschließlich des leeren Wortes) umfasst, bezeichnen wir mit .
Finite-State-Maschinen werden häufig verwendet, um bestimmte Eigenschaften von Wörtern zu bestimmen, d. h. zur Spracherkennung: Ein Automat, der eine bestimmte Sprache L erkennt, muss bei einem gegebenen beliebigen Wort w die Frage „?“ beantworten. Um ein solches Problem zu lösen, kann die Ausgabefunktion dadurch ersetzt werden, dass überprüft wird, in welchen Zustand die Maschine nach Empfang des Eingabeworts w übergeht – „akzeptieren“ oder „ablehnen“.
Definition 4.3. Deterministischer endlicher Automat (DFA) – Erkenner – ist ein System der Form
inklusive folgender Komponenten:
Die Funktion wird aufgerufen Programm Automat A und als Liste von m n angegeben Mannschaften Art 
.
Es ist auch praktisch, eine Funktion mithilfe der oben beschriebenen Tabelle der Größe n x m zu definieren, deren Zeilen den Zuständen von Q und deren Spalten den Symbolen von entsprechen Eingabealphabet und in dem am Schnittpunkt von Zeile q i und Spalte a j ein Zustand vorliegt.
Wie automatische Konverter Erkennerautomaten können mithilfe beschrifteter gerichteter Graphen, sogenannter Diagramme, dargestellt werden.
Definition 4.4. DKA-Diagramm ist ein gerichteter (Multi-)Graph D A =(Q, E) mit beschrifteten Kanten, in dem ein Knoten ausgewählt ist - Ausgangszustand q 0 Von jedem Scheitelpunkt aus gibt es Kanten, die mit Symbolen beschriftet sind, so dass es für jedes einzelne Symbol eine einzelne Kante von q zum Scheitelpunkt gibt 
mit Etikett a.
Nehmen wir an, dass der Pfad p=e 1 e 2 ... e t, der durch eine Folge von Kanten im Diagramm dargestellt wird, das Wort w=w 1 w 2 ... w t trägt, wenn w i die Bezeichnung der Kante e i (1 >= ist i >= t) . Wenn q der Anfangsscheitelpunkt (Zustand) dieses Pfades und q" sein Endscheitelpunkt ist, dann sagen wir, dass das Wort w q in q" übersetzt.
Arbeit Finite-State-Machine-Erkenner besteht darin, das Eingabewort zu lesen und den Zustand abhängig von seinen Symbolen zu ändern.
Definition 4.5. Lass uns anrufen DKA-Konfiguration ein beliebiges Paar der Form (q, w), in der und .
Auf einer Reihe von Konfigurationen führen wir die Übergangsrelation in einem Schritt ein:
Wenn, dann setzen wir für jedes: .
Bezeichnen wir reflexiv und Transitive Schließung .
Sinnvollerweise bedeutet dies, dass der Automat A nach einer endlichen Anzahl von Schritten 0 im Zustand q mit der Arbeit am Wort w=w 1 ... w l beginnt<= k <= l прочтет первые k символов слова w и перейдет в состояние q" , а w" =w k+1 ... w l - это непрочтенный остаток слова w .
Definition 4.6. DFA A erkennt (gibt zu, akzeptiert) das Wort w if für einige
Diese. Nach der Verarbeitung des Wortes w geht die Maschine in den Empfangszustand über.
Sprache L A, von einem Automaten erkannt (erlaubt, akzeptiert) werden A besteht aus allen von dieser Maschine erkannten Wörtern.
