Nicht-deterministische endliche Automaten in der Softwareentwicklung?

Die meisten regulären Ausdrucksmaschinen verwenden nicht -deterministische Automaten, da sie viel größere Flexibilität bieten. DFAs sind viel eingeschränkter. Sehen Sie sich einige Implementierungen an und Sie werden das sehen. Microsoft unterstreicht diese Tatsache sogar in ihrer Dokumentation des .NET Regex Klasse:

  

Die .NET Framework-Engine für reguläre Ausdrücke ist ein Backtracking-Matcher für reguläre Ausdrücke, der eine traditionelle NDE-Engine (Nondeterministic Finite Automaton) wie Perl, Python, Emacs und Tcl verwendet.

Übereinstimmendes Verhalten (erster Absatz) - dieser Artikel bietet auch an eine Begründung für den Einsatz eines NFA statt eines effizienteren EDA.

Wie Sie wissen, sind NFA und DFA rechnerisch gleichwertig. Es ist einer der ersten Sätze in der Automatentheorie. Es gibt Algorithmen zum Konvertieren (im Gegensatz zu Pushdown- oder Turing-Maschinen).

Also. Warum einer über den anderen? Weil die Darstellung eines bestimmten Problems mit einem NFA viel einfacher ist als das äquivalente DFA.

edit: Wenn es darum geht, die Maschine tatsächlich zu berechnen, werden DFAs schneller, weil sie nicht zurückverfolgen müssen. Aber sie werden mehr Speicher benötigen, um darzustellen. (Mem vs CPU-Kompromiss)

Mein Ratschlag = werfen Sie einen Blick in das Handbuch zu Adrian Thurstons Ragel .

Es gibt einfache Möglichkeiten, ein DFA direkt zu generieren, aber ich glaube, dass sie nur eine begrenzte Anzahl von Operatoren unterstützen - im Grunde genommen die üblichen EBNF-Verdächtigen. Ragel verwendet nicht-deterministische Methoden, um komplexe Automaten aus einfacheren zu konstruieren, und nutzt dann die Epsilon-Eliminierung und -Minimierung, um effiziente deterministische Automaten zu erzeugen. Egal wie viele seltsame Operatoren Sie benötigen, die Konvertierung in einen minimalen deterministischen Automaten ist immer gleich und jede Operatorimplementierung wird durch die Verwendung nichtdeterministischer Methoden einfach gehalten.

Der viterbi-Algorithmus funktioniert auf Hidden Markov Models , indem sie sie wie eine NFA behandeln. Nicht völlig identisch, aber sicherlich analog.

Sie sind nützlich in Anwendungen wie Sprache und Texterkennung.

Sehr oft ist es viel einfacher, ein NFA zu erstellen und dann damit zu arbeiten (der einzige Unterschied besteht darin, dass Sie eine Reihe von Zuständen anstelle eines Zustands halten). Wenn Sie es schnell haben wollen, können Sie DFA machen, aber vergessen Sie nicht, dass die Zeit dazu exponentiell ist (weil der resultierende Automat exponentiell größer sein kann!).

Andererseits, wenn Sie eine ergänzende Sprache machen wollen, haben Sie keine Wahl, Sie brauchen eine det. Variante.

Es ist der Grund, warum die Negation in keiner der regulären Ausdrucksmaschinen ist, nur in Klassen ([^ ...]), wo Sie sicher sein können, dass der Automat deterministisch ist.

Korrigiere mich, wenn ich falsch liege, aber von meiner Compiler-Klasse erinnere ich mich, dass du manchmal DFA einfach nicht benutzen kannst, da dies zu einer "Explosion" von Zuständen führen würde.

Ich denke, der Hauptgrund für die Wahl eines nicht-deterministischen endlichen Automaten wäre, das gewählte Match zurück zu bekommen. Es ist wahrscheinlich viel schwieriger, es mit einer deterministischen Version zu tun.

Wenn Sie nur wissen wollen, ob sie übereinstimmen oder nicht, und keine anderen Details, würde ich denken, dass das Kompilieren zu einem endlichen Automaten besser wäre.

Cayuga verwendet nicht-deterministische endliche Automaten unter der Haube für komplexe Ereignisverarbeitung. Nun, es sieht so aus, als nannten sie es "Stateful Publish / Subscribe für Event Monitoring", aber ich glaube es ist CEP.

Ich glaube, einige ihrer Arbeiten diskutieren sogar, warum sie ein Automatenmodell verwenden. Vielleicht möchten Sie ihre Website durchsuchen.

  

... Cayuga-Automaten, erweitert von nichtdeterministischen endlichen Automaten.