Können wir sagen, dass DFA effizienter ist als NFA?

Ich habe gerade angefangen, über die Theorie der Berechnung zu lesen. Wenn wir vergleichen, was (beim Akzeptieren von Zeichenfolgen) mächtiger ist, sind beide gleich. Aber wie steht es mit der Effizienz? DFA ist im Vergleich zu NFA schnell, da es nur eine ausgehende Flanke hat und keine Mehrdeutigkeit besteht. Aber im Falle von NFA müssen wir alle möglichen Fälle überprüfen und das braucht sicherlich Zeit. Können wir also sagen, dass DFA effizienter ist als NFA?

Aber mein anderer Teil des Gehirns denkt auch, dass NFA nur in der Theorie existiert, deshalb können wir seine Effizienz nicht mit DFA vergleichen.

Es gibt zwei Antworten, je nachdem, wie Sie effizient definieren.

Kompaktheit der Darstellung

Mit weniger mehr sagen: NFAs sind effizienter.

Das Konvertieren eines DFA in einen NFA ist unkompliziert und vergrößert die Darstellung nicht.

Es gibt jedoch reguläre Sprachen, für die der kleinste DFA exponentiell größer ist als der kleinste NFA. Ein typisches Beispiel ist für k fest.$(a|b)^*b(a|b)^k$$k$

Berechnung

Schnelle Ausführung: DFAs sind effizienter.

Die Computer, die wir heute benutzen, sind deterministischer Natur. Das macht sie schlecht im Umgang mit Nichtdeterminismus. Es gibt zwei übliche Methoden, um deterministisch mit NFAs umzugehen: das Zurückverfolgen auf einer Seite, was ziemlich kostspielig ist, oder das Verfolgen der aktiven Zustände, was bedeutet, dass jeder Übergang bis zu mal länger dauert (wobei N die Größe der NFA ist). .$N$$N$

In Bezug auf die Leistung sind sie äquivalent, wie Sie sagten, und es gibt einen Algorithmus (Teilmengenkonstruktion) zum Umwandeln eines NFA in einen äquivalenten DFA. Wie Sie dem Namen des Algorithmus entnehmen können, werden Teilmengen von Zuständen des NFA erstellt. Wenn Ihr NFA Zustände hat, gibt der Algorithmus möglicherweise einen DFA mit 2 n Zuständen aus, dies ist jedoch eine Obergrenze. Manchmal ändert sich die Anzahl der Zustände überhaupt nicht oder verringert sich sogar. In der Praxis ist es also weniger wichtig, welchen man verwendet.$n$$2^n$

Die DFA-Übereinstimmung ist in der Größe der Eingabezeichenfolge linear. Der NFA-Abgleich umfasst das Zurückverfolgen, damit NFAs mehr Arbeit leisten. Somit sind DFAs effizienter.

Fügen Sie einfach die obigen Antworten hinzu:

NFAs können in dem Sinne recheneffizienter als DFAs sein, dass sie auf einem Parallelprozessor simuliert werden können.

Übrigens: Ich sehe Leute sagen, dass NFAs in der Realität nicht existieren können. Ich bin anderer Ansicht. Ein Computer mit einer großen Anzahl von Prozessoren kann viele Aufgaben parallel ausführen und kann als nicht deterministische Maschine betrachtet werden. Man könnte jeden Berechnungszweig einem neuen Prozessor zuweisen und sie alle anhalten, wann immer einer von ihnen akzeptiert.

$\epsilon$

Wie andere angemerkt haben, müssen Sie definieren, was "Effizienz" bedeutet. Um dies zu veranschaulichen, gebe ich ein vernünftiges Modell mit einer anderen Antwort.

Betrachtet man nur die Automatenmodelle, bei denen insbesondere außer Acht gelassen wird, wie sie auf realen Maschinen implementiert werden, so ist das offensichtliche Effizienzmaß die "Anzahl der Übergänge, die bei einem (kürzesten) akzeptierenden Durchlauf ausgeführt werden".

$\varepsilon$

Technisch gesehen ist ein NFA ein allgemeineres Konzept als ein DFA, da es nicht erforderlich ist, den Nichtdeterminismus zu verwenden. Mit anderen Worten: Jeder DFA ist ein NFA. Aus dieser Perspektive gibt es für jede Sprache eine NFA, die mindestens so effizient ist wie die effizienteste DFA, unabhängig davon, welche Effizienzmaßnahme Sie bevorzugen.

Abgesehen davon stimme ich Raphael zu, dass es sehr stark darauf ankommt, was Sie mit Effizienz und Umsetzung meinen .

Wie wir von Automaten wissen, dh Maschinen, die jede Handlung ohne menschliche Kraft oder ohne direkte Beteiligung des Menschen ausführen können. zB: Waschmaschine. Endliche Automaten bedeuten, dass wir wissen, wie viele Aufgaben maschinell ausgeführt werden: 1 EIN drücken 2 AUS drücken, sodass es nur zwei Zustände gibt, dh endliche Automaten. Kommen wir nun zu DFA, dh deterministischen endlichen Automaten. Formal bedeutet dies, dass wir leicht feststellen können, dass Zustände keine Mehrdeutigkeit aufweisen und informell nur ein Übergang für ein Symbol zulässig ist. NFA: nicht deterministische endliche Automaten. Es wird mehr Zeit benötigt, um den tatsächlichen Zustand zu berechnen, und es gibt Mehrdeutigkeiten. Informell heißt es, dass für ein Symbol mehrere Übergänge zulässig sind. Wenn die Zeit zum Erreichen des Ziels verstrichen ist, benötigt NFA mehr Zeit als DFA, aber NFA kann mehr Daten als DFA laden. * DFA und NFA haben die gleiche Fähigkeit, die Zeichenfolge zu erkennen. Danke. Deepali Kaushik