Ich weiß, dass wir DFAs minimieren können, indem wir äquivalente Zustände finden und zusammenführen, aber warum können wir das nicht auch mit NFAs tun? Ich suche keinen Beweis oder ähnliches - es sei denn, ein Beweis ist einfacher zu verstehen. Ich möchte nur intuitiv verstehen, warum die NFA-Minimierung so schwierig ist, wenn die DFA-Minimierung dies nicht ist.
Für DFA gibt es eine schöne algebraische Struktur, die bestimmt, welche Zustände äquivalent sein können. Die Myhill-Nerode-Äquivalenz für Zeichenfolgen hängt mit der Minimierung von DFA zusammen.
Für NFA ist die Situation kompliziert, da es im Allgemeinen keine eindeutige minimale NFA gibt.
Hier ist ein Beispiel für die endliche Sprache . Die beiden Automaten sind beide state-minimal. Das Beispiel stammt aus dem Aufsatz Eine Anmerkung zu minimalen nicht deterministischen Automaten von Arnold, Dicky und Nivat.
Diese Antwort versucht zum Ausdruck zu bringen, dass die beiden Probleme "technisch" unterschiedlich sind. Siehe die Antwort von vzn für Details, wie sich die Probleme in der Rechenkomplexität unterscheiden.
Sie haben nach einer intuitiven Einstellung gefragt.
In einem DFA kann ein bestimmtes Eingabepräfix höchstens einen Zustand erreichen. Man kann dann Paare von Zuständen zusammenführen, die für ein beliebiges Suffix nicht zu unterscheiden sind. Zustände, die durch ein Suffix unterschieden werden können, können nicht zusammengeführt werden. Dies führt zu einem Minimalautomaten, der zu allen anderen Minimalautomaten isomorph ist.
quelle
Siehe auch diese TCS.se-Frage zur Berechnung der minimalen NFA für eine DFA
quelle