Wie normalisieren Sie einen endlichen Automaten?

Question

1. Wie finden Sie die minimale deterministische FSM?
2. Gibt es eine Möglichkeit nicht-deterministisch FSMs zu normalisieren?
3. Sie haben eine lineare Zeit gebunden Algorithmus, um die minimale FSM für eine bestimmte Maschine zu finden?
4. Gibt es eine Möglichkeit zu sehen, ob zwei FSMs gleichwertig sind?

Dies ist keine Hausaufgaben Frage. Ich beobachtete diese Vortragsreihe und nur neugierig geworden.

Answer 1

Einige informelle Antworten Sie die Ideen zu geben, für detaillierte Beweise lesen ein gutes Buch über Automata, zum Beispiel dieses oder die in den anderen Antworten erwähnten. Und ich bin mir ziemlich sicher, es gibt Online-Material, das Sie alle Ihre Fragen finden können, zu beantworten.

• Wie finden Sie die minimale deterministische FSM?

Das Verfahren ist duplizierten Zustände zu eliminieren (oder äquivalente Zustände zu verschmelzen). Sie wissen, dass Zustand und Übergänge sind die Schlüssel zum Saiten zu erzeugen. Grundsätzlich dupliziert Staaten tragen nicht die Sprache bei der Herstellung erzeugte eine größere oder weniger. Der Algorithmus beginnt von Endzuständen, die immer die Möglichkeit haben, von der Lamda (leere Zeichenkette) zu erzeugen, und rekursiv eine Tabelle aktualisieren, die die Fähigkeit zur Erzeugung eines Staates zeigen, und verschmelzen schließlich jene Staaten keinen Unterschied machen.

• Gibt es eine Möglichkeit nicht-deterministisch FSMs zu normalisieren?

Die normalisierte DFA für die NFA wird mit verschiedenen Sammlungen der Zustände von NFA als DFA Staaten zum Beispiel {Zustand 0} - (1) -> {state1, state2}, um den nicht-deterministischen Teil zu entfernen, gibt es keine Art und Weise des Zustand Explosion zu vermeiden, da DFA hat, das zu tun, die Sprache zu repräsentieren.

• Sie haben eine lineare Zeit gebunden Algorithmus, um die minimale FSM für eine bestimmte Maschine zu finden?

Ich erinnere mich die beste ist O (n log n) durch ein paar Tricks zu tun, von einem Western Ontario Universität Professor Informationen in etwas Papier Wiederverwendung und Zweifel gibt bessere existiert. Ich glaube, dass die klassischen ein O (N ^ 2) ist.

• Gibt es eine Möglichkeit zu sehen, ob zwei FSMs gleichwertig sind?

Ja. Holen Sie sich das minimal ein, Code, um den Zustand von ihrem Zugriff auf String (eine Zeichenkette, die den Zustand von dem Startzustand erreichen konnte, das ist so ziemlich der echte „Name“ einen Staates dort), und überprüfen Sie den Übergang Karte. Es könnten bessere Möglichkeiten, obwohl sein, aber es würde kein großer Unterschied auf der BIGO sein.

Answer 2

Da alle nichtdeterministische FSM eine coresponding deter FSM haben, ist die Antwort auf den Abschnitten 1 und 2 sollte gleich sein.

Wenn Sie mehr wissen möchten, erhalten eine Kopie „Einführung in die Theorie der Berechnung“ von Michael Sipser, die ein wirklich großes Buch ist es, diese Dinge zu lernen. Sipser weiß, was er spricht über und , wie es kommunizieren sehr gut.

Answer 3

• Wenn Sie einige deterministische FSM gegeben sind, dann können Sie eine gleichwertige, minimal ein mit einem recht einfachen Algorithmus in O finden (n ² ); Hopcroft Algorithmus tut es in O (n log n). Hier Sie Beschreibung der beiden finden. Sie können prüfen, ob A und B äquivalent sind, von ihnen zu minimieren und zu überprüfen, ob sie gleich sind.
• Wenn Sie einige nichtdeterministische FSM gegeben, so ein äquivalentes finden, minimal ist PSPACE-complete . Mit anderen Worten, es wird kein guter Algorithmus bekannt und wird vermutet, dass es nicht existiert. Überprüfen Gleichwertigkeit von zwei nichtdeterministische Automata ist PSPACE-vollständig zu. Also, es sei denn es eine sehr unwahrscheinlich Durchbruch sein wird, sollten Sie den Automaten auf eine determinis konvertieren (das dauert viel Zeit) und dann Überprüfungen durchführen.
• Sie können eine nichtdeterministische FSM auf eine determinis mit exponentieller Anzahl von Zuständen zu transformieren. Dies ist unvermeidbar. Übung (nicht schwer!): Die Sprache, bestehend aus Worten, in dem der n-ten Brief vom Ende „a“ kann unter Verwendung eines nichtdeterministische FSM mit n Staaten anerkannt werden, und es nicht erkannt wird unter Verwendung von eine deterministische FSM mit weniger als 2 ⁿ Staaten. Exponential gebundene kann im allgemeinen Fall nicht gebrochen werden.

Answer 4

Überprüfen Sie "Grundlagen der Compiler Design" im Abschnitt beginnen 2.5. Erhältlich kostenlos online. http://www.diku.dk/hjemmesider/ansatte/torbenm/ Basics / basics_lulu.pdf

Es umfasst eine NFA zu einem DFA Umwandlung und die DFA zu minimieren. NFAs kann exponentiell erweitern, wenn zu DFAs umgewandelt.

“... jede reguläre Sprache (eine Sprache das kann durch einen regulären Ausdruck ausgedrückt werden, NFA oder DFA) eine eindeutige minimale DFA. Daher können wir die Gleichwertigkeit von regulären Ausdrücken entscheiden (oder NFAs oder DFAs) durch beide minimal DFAs Umwandlung und die Ergebnisse vergleichen.“