Deterministische endliche Automaten

Ein Beispiel für einen deterministischen endlichen Automaten, der nur binäre Zahlen akzeptiert, die ein Vielfaches von 3 Jahren sind S₀ ist sowohl der Startstaat als auch ein Akzeptanzstaat. Zum Beispiel führt die Zeichenfolge "1001" zur Zustandssequenz S₀, S₁, S₂, S₁, S₀, und ist daher akzeptiert.

In dem Theorie der Berechnungein Zweig von Theoretische Informatik, a Deterministische endliche Automaten (DFA)-auch bekannt als deterministischer endlicher Akzeptor (DFA), deterministische Finite-State-Maschine (DFSM), oder Deterministischer Finite-State-Automaten (DFSA)-ist ein Finite-State-Maschine das akzeptiert oder ablehnt eine gegebene Saite von Symbolen, indem durch eine Zustandssequenz durch die Zeichenfolge bestimmt wird.^[1] Deterministisch bezieht sich auf die Einzigartigkeit des Berechnungslaufs. Auf der Suche nach den einfachsten Modellen zum Erfassen von Finite-State-Maschinen, Warren McCulloch und Walter Pitts gehörten zu den ersten Forschern, die 1943 ein Konzept wie endliche Automaten einführten.^[2][3]

Die Abbildung zeigt einen deterministischen endlichen Automat mit a Zustandsdiagramm. In diesem Beispiel gibt es drei Staaten: s₀, S₁und s₂ (Grafisch durch Kreise bezeichnet). Der Automaten nimmt ein endlich Reihenfolge von 0s und 1s als Eingabe. Für jeden Zustand gibt es einen Übergangspfeil, der für 0 und 1. zu einem nächsten Zustand führt. Beim Lesen eines Symbols springt ein DFA deterministisch von einem Zustand zum anderen, indem Sie dem Übergangspfeil folgen. Zum Beispiel, wenn sich der Automaton derzeit in Bundesstaat befindet₀ und das aktuelle Eingangssymbol ist 1, dann springt es deterministisch, dass s angibt s s.₁. Ein DFA hat eine Staat starten (bezeichnet grafisch durch einen Pfeil aus dem Nichts), wo Berechnungen beginnen und a einstellen von Staaten akzeptieren (bezeichnet grafisch durch einen Doppelkreis), die dazu beitragen, zu definieren, wann eine Berechnung erfolgreich ist.

Ein DFA wird als abstraktes mathematisches Konzept definiert, wird jedoch häufig in Hardware und Software zur Lösung verschiedener spezifischer Probleme wie z. lexikalische Analyse und Musteranpassung. Beispielsweise kann eine DFA -Software modellieren, die entscheidet, ob Online -Benutzereingaben wie E -Mail -Adressen syntaktisch gültig sind oder nicht.^[4]

DFAs wurden verallgemeinert auf Nichtdeterministische endliche Automaten (NFA) Dies kann mehrere Pfeile desselben Etiketts aus einem Zustand aus haben. Verwendung der Poweret -Konstruktion Methode, jede NFA kann in eine DFA übersetzt werden, die dieselbe Sprache erkennt. DFAs und NFAs erkennen genau genau den Satz von reguläre Sprachen.^[1]

Formale Definition

Ein deterministischer endlicher Automaton M ist eine 5-Tupel, (Q, Σ, δ, q₀, F), bestehend aus

• eine endliche Menge von Zustände Q
• Ein endlicher Satz von Eingabymbolen, die als die genannt werden Alphabet Σ
• ein Übergang Funktion δ: Q × σ → Q
• ein Anfang oder Staat starten ${\ displayStyle q_ {0} \ in q}$
• eine Menge von Staaten akzeptieren ${\ displayStyle f \ subseteq q}$

Lassen w = a₁a₂…a_n Sei eine Saite über dem Alphabet Σ. Der Automat M Akzeptiert die Zeichenfolge w Wenn eine Abfolge von Zuständen, r₀, r₁,…, r_n, existiert in Q mit den folgenden Bedingungen:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), zum i = 0,…, n - 1
3. ${\ displayStyle r_ {n} \ in f}$.

In Worten besagt die erste Bedingung, dass die Maschine im Startzustand beginnt q₀. Die zweite Bedingung besagt, dass bei jedem Zeichen der Zeichenfolge angegeben wird w, Die Maschine wechselt von Zustand zu Zustand gemäß der Übergangsfunktion δ. Die letzte Bedingung besagt, dass die Maschine akzeptiert w Wenn der letzte Eingang von w bewirkt, dass die Maschine in einem der akzeptierenden Zustände anhält. Ansonsten wird gesagt, dass der Automaten lehnt ab die Saite. Die Saiten, die M Akzeptiert ist das Sprache anerkannt durch M und diese Sprache wird von bezeichnet durch L(M).

Ein deterministischer endlicher Automat ohne Akzeptieren von Zuständen und ohne Startzustand ist als a bekannt Übergangssystem oder Semiautomaton.

Eine umfassendere Einführung der formalen Definition finden Sie unter Automatenheorie.

Beispiel

Das folgende Beispiel ist eine DFA Mmit einem binären Alphabet, das erfordert, dass die Eingabe eine gleichmäßige Anzahl von 0s enthält.

Das Zustandsdiagramm zum M

M = (Q, Σ, δ, q₀, F) wo

• Q = {{S₁, S₂}
• Σ = {0, 1}
• q₀ = S₁
• F = {{S₁} und
• δ wird durch Folgendes definiert Zustandsübergangstabelle:

	0	1
S1	S2	S1
S2	S1	S2

Der Staat S₁ stellt dar, dass es bisher eine gleiche Anzahl von 0er in der Eingabe gab S₂ bedeutet eine ungerade Zahl. Eine 1 im Eingang ändert den Status des Automatens nicht. Wenn der Eingang endet, zeigt der Zustand an, ob die Eingabe eine gleichmäßige Anzahl von 0s enthält oder nicht. Wenn der Eingang eine gleichmäßige Anzahl von 0s enthielt, M wird im Staat fertig sein S₁, ein Akzeptanzstatus, so dass die Eingangszeichenfolge akzeptiert wird.

Die Sprache, die von erkannt wurde M ist der Regelmäßige Sprache gegeben durch die regulären Ausdruck (1*) (0 (1*) 0 (1*))*, wo * ist der Kleene Star, z.B., 1* bezeichnet eine beliebige Zahl (möglicherweise null) von aufeinanderfolgenden.

Variationen

Vollständig und unvollständig

Gemäß der obigen Definition sind deterministische endliche Automaten immer Komplett: Sie definieren aus jedem Zustand einen Übergang für jedes Eingabetriebsymbol.

Während dies die häufigste Definition ist, verwenden einige Autoren den Begriff deterministischer endlicher Automat für einen etwas anderen Begriff: einen Automat, der sich definiert maximal ein Übergang für jeden Zustand und jedes Eingabetriebsymbol; Die Übergangsfunktion darf sein teilweise.^[5] Wenn kein Übergang definiert ist, hält ein solcher Automat an.

Lokale Automaten

A Lokaler Automaten ist eine DFA, nicht unbedingt abgeschlossen, für die alle Kanten mit demselben Etikett zu einem einzigen Scheitelpunkt führen. Lokale Automaten akzeptieren die Klasse von Lokalsprachen, diejenigen, für die Mitgliedschaft eines Wortes in der Sprache durch ein "Schiebfenster" der Länge zwei auf dem Wort bestimmt wird.^[6][7]

A Myhill Graph über einem Alphabet A ist ein gerichteter Graph mit Scheitelpunktset A und Teilmengen von Scheitelpunkten mit der Bezeichnung "Start" und "Finish". Die von einem Myhill -Diagramm akzeptierte Sprache ist der Satz von gerichteten Pfaden von einem Startscheitel bis zu einem Finish -Scheitelpunkt: Der Diagramm fungiert somit als Automat.^[6] Die von Myhill Graphs akzeptierte Sprachenklasse ist die Klasse der lokalen Sprachen.^[8]

Zufälligkeit

Wenn der Startzustand und die Akzeptanzstaaten ignoriert werden, eine DFA von n Zustände und ein Alphabet der Größe k kann als als gesehen werden Digraph von n Scheitelpunkte, bei denen alle Scheitelpunkte haben k Out-Arcs beschriftet 1,…, k (a k-Out Digraph). Es ist bekannt, dass wenn k ≥ 2 ist eine feste Ganzzahl mit hoher Wahrscheinlichkeit, die größte stark verbundene Komponente (SCC) in einem solchen k-OUT Digraph, das gleichmäßig nach dem Zufallsprinzip ausgewählt wurde, ist von linearer Größe und kann von allen Scheitelpunkten erreicht werden.^[9] Es wurde auch bewiesen, dass wenn k darf sich erhöhen als n Erhöht sich, dann hat der gesamte Digraph einen Phasenübergang für eine starke Konnektivität ähnlich wie ERDős -Rényi -Modell Für Konnektivität.^[10]

In einem zufälligen DFA liegt die maximale Anzahl von Scheitelpunkten, die von einem Scheitelpunkt erreichbar sind SCC mit hoher Wahrscheinlichkeit.^[9][11] Dies gilt auch für das größte induzierter Sub-Digraph von minimaler Grad, der als gerichtete Version von gesehen werden kann 1-Ader.^[10]

Verschlusseigenschaften

Der obere linke Automaton erkennt die Sprache aller binären Zeichenfolgen, die mindestens ein Vorkommen von "00" enthalten. Der untere rechte Automaton erkennt alle binären Saiten mit einer gleichmäßigen Anzahl von "1". Der untere linke Automat wird als Produkt der ersteren beiden erhalten, er erkennt den Schnittpunkt beider Sprachen.

Wenn DFAs die Sprachen erkennen, die durch Anwenden einer Operation auf den dfa -erkennbaren Sprachen erhalten werden, sollen DFAs bezeichnet werden unter geschlossen die Operation. Die DFAs sind im Rahmen der folgenden Operationen geschlossen.

Für jede Operation wurde ein optimaler Konstruktion in Bezug auf die Anzahl der Zustände in festgelegt Zustandskomplexität Forschung. Da dfas sind Äquivalent zu Nichtdeterministische endliche Automaten (NFA) können diese Schließungen auch unter Verwendung von Verschlusseigenschaften von NFA nachgewiesen werden.

Als Übergang Monoid

Ein Lauf eines bestimmten DFA kann als Folge von Zusammensetzungen einer sehr allgemeinen Formulierung der Übergangsfunktion mit sich selbst angesehen werden. Hier konstruieren wir diese Funktion.

Für ein bestimmtes Eingangssymbol ${\ displayStyle a \ in \ sigma}$, man kann eine Übergangsfunktion konstruieren ${\ displayStyle \ Delta _ {a}: q \ rightarrow q}$ durch Definition ${\ displayStyle \ delta _ {a} (q) = \ delta (q, a)}$ für alle ${\ displayStyle q \ in q}$. (Dieser Trick heißt Currying.) Aus dieser Perspektive, ${\ displayStyle \ Delta _ {a}}$ "Handlungen" eines Staates in Q, um einen anderen Staat zu ergeben. Man kann dann das Ergebnis von betrachten Funktionszusammensetzung wiederholt auf die verschiedenen Funktionen angewendet ${\ displayStyle \ Delta _ {a}}$, ${\ displayStyle \ Delta _ {B}}$, usw. Ein paar Buchstaben gegeben ${\ displayStyle a, b \ in \ sigma}$, man kann eine neue Funktion definieren $oder$, wo ${\ displayStyle \ circ}$ bezeichnet die Funktionszusammensetzung.

Dieser Prozess kann eindeutig rekursiv fortgesetzt werden, was die folgende rekursive Definition von ergibt $oder$:

${\ displayStyle {\ WideHat {\ delta}} (q, \ epsilon) = q}$, wo ${\ displayStyle \ Epsilon}$ ist die leere Zeichenfolge und

$oder$, wo ${\ displayStyle w \ in \ sigma ^{*}, a \ in \ sigma}$ und ${\ displayStyle q \ in q}$.

${\ displayStyle {\ WideHat {\ delta}}}$ ist für alle Wörter definiert ${\ displayStyle w \ in \ sigma ^{*}}$. Ein Lauf des DFA ist eine Folge von Kompositionen von ${\ displayStyle {\ WideHat {\ delta}}}$ mit sich selbst.

Wiederholte Funktionszusammensetzung bildet a Monoid. Für die Übergangsfunktionen ist dieses Monoid als das bekannt Übergang Monoidoder manchmal das Transformationssemigroup. Die Konstruktion kann auch umgekehrt werden: gegeben a ${\ displayStyle {\ WideHat {\ delta}}}$, man kann a rekonstruieren ${\ displayStyle \ Delta}$und so sind die beiden Beschreibungen gleichwertig.

Vorteile und Nachteile

DFAs sind eines der praktischsten Berechnungsmodelle, da es eine triviale lineare Zeit gibt, konstanter Raum, Online -Algorithmus Simulieren Sie einen DFA auf einem Eingangsstrom. Außerdem gibt es effiziente Algorithmen, um ein DFA zu erkennen:

• Die von einer bestimmten DFA erkannte Sprache.
• Die Vereinigung/Schnittstelle der von zwei angegebenen Sprachen, die von zwei dfas anerkannt sind.

Weil DFAs auf a reduziert werden können kanonische Form (Minimale DFAs) Es gibt auch effiziente Algorithmen zu bestimmen:

• Ob eine DFA irgendwelche Zeichenfolgen akzeptiert (Leeresproblem)
• Ob eine DFA alle Zeichenfolgen akzeptiert (Universalitätsproblem)
• Ob zwei DFAs dieselbe Sprache erkennen (Gleichheitsproblem)
• Ob die von einer DFA erkannte Sprache in der von einem zweiten DFA erkannten Sprache (Einschlussproblem) enthalten ist
• Die DFA mit einer Mindestanzahl von Zuständen für eine bestimmte reguläre Sprache (Minimierungsproblem)

DFAs sind gleichbedeutend mit der Rechenleistung zu Rechenleistung zu Nichtdeterministische endliche Automaten (NFAS). Dies liegt daran, dass jeder DFA auch eine NFA ist, sodass eine NFA das tun kann, was eine DFA kann. Auch bei einem NFA die Verwendung der Poweret -Konstruktion Man kann eine DFA bauen, die dieselbe Sprache wie die NFA erkennt, obwohl die DFA eine exponentiell größere Anzahl von Zuständen als die NFA haben könnte.^[13][14] Obwohl NFAs mit DFAs rechnerisch äquivalent sind, werden die oben genannten Probleme auch für NFAs nicht unbedingt effizient gelöst. Das Problem der Nicht-Universalität für NFAs ist PSPACE vollständig Da es kleine NFAs mit kürzester abgelehntem Wort in exponentieller Größe gibt. Ein DFA ist universell, wenn und nur wenn alle Staaten endgültige Zustände sind, dies gilt jedoch nicht für NFAs. Die Gleichheit, Einschluss- und Minimierungsprobleme sind ebenfalls abgeschlossen, da sie die Ergänzung einer NFA bilden müssen, was zu einer exponentiellen Größe der Größe führt.^[15]

Andererseits sind Finite-State-Automaten in den Sprachen, die sie erkennen können, von streng begrenztem Kraft. Viele einfache Sprachen, einschließlich eines Problems, das mehr als ständigen Raum erfordert, können von einem DFA nicht erkannt werden. Das klassische Beispiel einer einfach beschriebenen Sprache, die kein DFA erkennen kann Dyck -Sprache, d.h. die Sprache, die aus ordnungsgemäß gepaarten Klammern wie Wort "(() ()) besteht. Intuitiv kann kein DFA die Dyck-Sprache erkennen, da DFAs nicht zählen können: Ein DFA-ähnlicher Automat muss einen Zustand haben, um eine mögliche Anzahl von "derzeit offenen" Klammern darzustellen, was bedeutet, dass eine unbegrenzte Anzahl von Zuständen unbegrenzt werden würde. Ein weiteres einfacheres Beispiel ist die Sprache, die aus Strings der Form besteht aⁿbⁿ für einige endliche, aber willkürliche Anzahl von a's, gefolgt von einer gleichen Anzahl von b's.^[16]

DFA -Identifikation aus beschrifteten Wörtern

Bei einem Satz von einem Satz von positiv Wörter ${\ displayStyle S ^{+} \ subset \ sigma ^{*}}$ und ein Satz von Negativ Wörter ${\ displayStyle S ^{-} \ subset \ sigma ^{*}}$ Man kann eine DFA konstruieren, die alle Wörter akzeptiert ${\ displayStyle S^{+}}$ und lehnt alle Wörter aus ${\ displayStyle S^{-}}$: Dieses Problem heißt DFA -Identifizierung (Synthese, Lernen). Während etwas DFA kann in der linearen Zeit konstruiert werden. Das Problem der Identifizierung eines DFA mit der minimalen Anzahl von Zuständen ist eine NP-Vervollständigung.^[17] Der erste Algorithmus für die minimale DFA -Identifizierung wurde von Trakhtenbrot und Barzdin in vorgeschlagen^[18] und heißt das TB-Algorithmus. Der TB-Algorithmus geht jedoch davon aus, dass alle Wörter von ${\ displayStyle \ sigma}$ bis zu einer bestimmten Länge sind in beiden ${\ displayStyle S^{+} \ Cup S^{-}}$.

Später schlug K. Lang eine Erweiterung des TB-Algorithmus vor, der keine Annahmen über verwendet ${\ displayStyle S^{+}}$ und ${\ displayStyle S^{-}}$ das Traxbar Algorithmus.^[19] Traxbar garantiert jedoch nicht die Minimalität der konstruierten DFA. In seiner Arbeit^[17] E. M. Gold schlug auch einen heuristischen Algorithmus für die minimale DFA -Identifizierung vor. Golds Algorithmus nimmt das an ${\ displayStyle S^{+}}$ und ${\ displayStyle S^{-}}$ enthalten a charakteristische Set der regulären Sprache; Andernfalls ist die konstruierte DFA entweder inkonsistent mit ${\ displayStyle S^{+}}$ oder ${\ displayStyle S^{-}}$. Andere bemerkenswerte DFA -Identifikationsalgorithmen umfassen den RPNI -Algorithmus.^[20] Der blau-rensige evidenzgesteuerte staatlich-bergene Algorithmus,^[21] Fenster-edsm.^[22] Eine andere Forschungsrichtung ist die Anwendung von Evolutionsalgorithmen: Der evolutionäre Algorithmus zur Kennzeichnung von Smart State kennzeichnet^[23] Erlaubt, ein geändertes DFA -Identifikationsproblem zu lösen, bei dem die Trainingsdaten (Sets ${\ displayStyle S^{+}}$ und ${\ displayStyle S^{-}}$) ist laut in dem Sinne, dass einige Wörter auf falsche Klassen zugeschrieben werden.

Ein weiterer Schritt nach vorne ist auf die Anwendung von der Anwendung von zurückzuführen Sa Löser von Marjin J. H. Heule und S. Verwer: Das Problem der minimalen DFA -Identifizierung wird auf die Entscheidung der Erfüllbarkeit einer booleschen Formel reduziert.^[24] Die Hauptidee besteht darin, einen erweiterten Präfix-Tree-Akzeptor (a) zu erstellen Trie enthält alle Eingabewörter mit entsprechenden Beschriftungen) basierend auf den Eingangssätzen und reduzieren das Problem beim Finden eines DFA mit ${\ displayStyle c}$ Staaten zu Färbung der Baumschützer mit ${\ displayStyle c}$ Staaten so, dass der generierte Automat deterministisch ist, wenn Scheitelpunkte mit einer Farbe zu einem Zustand verschmolzen werden, und passt zu ${\ displayStyle S^{+}}$ und ${\ displayStyle S^{-}}$. Obwohl dieser Ansatz das Auffinden der minimalen DFA ermöglicht, leidet er unter exponentieller Ausblasung der Ausführungszeit, wenn die Größe der Eingabedaten zunimmt. Daher wurde der anfängliche Algorithmus von Heule und Verwer später vor der Ausführung von SAT -Solver mehrere Schritte des EDSM -Algorithmus erweitert: der DFASAT -Algorithmus.^[25] Dies ermöglicht die Reduzierung des Suchraums des Problems, führt jedoch zum Verlust der Minimalitätsgarantie. Eine andere Möglichkeit, den Suchraum zu reduzieren, wurde in vorgeschlagen^[26] mittels neuer Symmetrie -Brechen Prädikate basierend auf der Breite-First-Suche Algorithmus: Die gesuchten DFA -Staaten sind gemäß dem vom Ausgangszustand gestarteten BFS -Algorithmus beschränkt. Dieser Ansatz reduziert den Suchraum durch ${\ displayStyle c!}$ durch Eliminierung isomorpher Automaten.

Äquivalente Modelle

Schreibgeschützte rechtsbewegte Turing-Maschinen

Schreibgeschützte rechtsbewegte Turing-Maschinen sind eine bestimmte Art von Turing Maschine das bewegt sich nur nach rechts; Diese entsprechen fast genau zu DFAs.^[27] Die Definition basierend auf einem einzig unendlichen Band ist ein 7-Tupel

${\ displayStyle m = \ Langle q, \ gamma, b, \ sigma, \ delta, q_ {0}, f \ rangle,}$

wo

${\ displayStyle q}$ ist ein endlicher Satz von Zustände;

${\ displayStyle \ gamma}$ ist ein endlicher Satz der Band Alphabet/Symbole;

${\ displayStyle b \ in \ gamma}$ ist der leeres Symbol (Das einzige Symbol, das auf dem Klebeband in jedem Schritt während der Berechnung häufig auftreten kann);

${\ displayStyle \ sigma}$, eine Teilmenge von ${\ displayStyle \ gamma}$ nicht inklusive b, ist der Satz von Eingabymbole;

$oder$ ist ein Funktion genannt Übergangsfunktion, R ist eine rechte Bewegung (eine rechte Verschiebung);

${\ displayStyle q_ {0} \ in q}$ ist der Ausgangszustand;

${\ displayStyle f \ subseteq q}$ ist der Satz von Finale oder Staaten akzeptieren.

Die Maschine akzeptiert immer eine reguläre Sprache. Es muss mindestens ein Element des Satzes existieren F (a HALT Staat) damit die Sprache nicht leer ist.

Beispiel einer 3-staatlichen 2-symbol-schreibgeschützten Turing-Maschine

${\ displayStyle q = \ {a, b, c, {\ text {halt}} \};};$

${\ displayStyle \ gamma = \ {0,1 \};}$

${\ displayStyle b = 0}$, "leer";

${\ displayStyle \ sigma = \ varnothing}$, leeres Set;

${\ displayStyle \ delta =}$ Siehe oben staatlicher Tisch;

${\ displayStyle q_ {0} = a}$, Ausgangszustand;

${\ displayStyle f =}$ Das einzige Element der letzten Zustände: ${\ displaystyle \ {{\ text {halt}} \}}$.

Siehe auch

Anmerkungen

Verweise

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Einführung in die Automatentheorie, Sprachen und Berechnung (2 ed.). Addison Wesley. ISBN 0-201-44124-1. Abgerufen 19. November 2012.
• Lawson, Mark V. (2004). Finite Automaten. Chapman und Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• McCulloch, W. S.; Pitts, W. (1943). "Ein logischer Berechnung der Ideen, die in nervöser Aktivität immanent sind". Bulletin der mathematischen Biophysik. 5 (4): 115–133. doi:10.1007/bf02478259. PMID 2185863.
• Rabin, M. O.; Scott, D. (1959). "Endliche Automaten und ihre Entscheidungsprobleme". IBM J. Res. Dev. 3 (2): 114–125. doi:10.1147/rd.32.0114.
• Sakarovitch, Jacques (2009). Elemente der Automata -Theorie. Übersetzt aus den Franzosen von Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Sipser, Michael (1997). Introduction to the Theory of Computation. Boston: PWS. ISBN 0-534-94728-x.. Abschnitt 1.1: Finite Automata, S. 31–47. Unterabschnitt "Dekable Probleme in Bezug auf reguläre Sprachen" von Abschnitt 4.1: Langlebige Sprachen, S. 152–155.4.4 DFA kann nur reguläre Sprache akzeptieren