Minimieren von Automaten, die

Was ist der Standardansatz zur Minimierung von Büchi-Automaten (oder auch Müller-Automaten)? Das Übertragen der üblichen Technik von endlichen Wörtern, dh das Setzen von zwei Zuständen auf Gleichheit, wenn die Wörter "Auslaufen" der akzeptierten Zustände gleich sind, funktioniert nicht. Stellen Sie sich zum Beispiel vor, dass das Büchi-Automoton alle Wörter mit einer unendlichen Anzahl von a akzeptiert, die aus zwei Zuständen bestehen, einem Anfangszustand und einem Endzustand, und der Endzustand jedes Mal eingegeben wird, wenn ein a gelesen wird, und der Anfangszustand jedes Mal eingegeben wird, wenn a anderes Symbol wird gelesen. Beide Zustände werden durch die obige Definition als gleich angesehen, aber wenn sie zusammenfallen, werden Automaten erhalten, die aus einem einzelnen Zustand bestehen und dadurch jedes Wort akzeptieren.

Im Allgemeinen haben $\omega$ reguläre Sprachen möglicherweise keine eindeutige minimale DBW. Zum Beispiel hat die Sprache "unendlich viele a und unendlich viele b" zwei DBWs mit drei Zuständen (im Bild ersetzen Sie $\neg a$ durch $b$ ):

Wie Sie sehen können, sind sie topologisch nicht äquivalent.

Daher ist das Minimierungsproblem schwieriger als der endliche Fall, und tatsächlich ist es NP-vollständig .

Diese Frage hat in den 80er Jahren viel Literatur hervorgebracht, was teilweise auf eine schlechte Herangehensweise an das Problem zurückzuführen ist. Dies ist eine ziemlich lange Geschichte, die ich in dieser Antwort zusammenfassen möchte.

1. Der Fall endlicher Wörter

In der Literatur finden sich zwei Definitionen eines minimalen DFA. Der erste besteht darin, den minimalen DFA einer regulären Sprache als den vollständigen DFA mit der minimalen Anzahl von Zuständen zu definieren, die die Sprache akzeptieren. Die zweite ist länger zu definieren, aber mathematisch ansprechender als die erste und bietet stärkere Eigenschaften.

Erinnern wir uns daran , dass ein DFA ist zugänglich , wenn für alle q ∈ Q , es ist ein Wort u ∈ A * , so dass i ⋅ u = q . Es ist vollständig, wenn q ⋅ a für alle q ∈ Q und a ∈ A definiert ist .$(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Sei und A 2 = ( Q 2 , A , ⋅ , i 2 , F 2 ) zwei vollständige, zugängliche DFAs. Ein Morphismus von A 1 nach A 2 ist eine Funktion φ : Q 1 → Q 2, so dass${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. ,$\varphi(i_1) = i_2$
2. ,$\varphi^{-1}(F_2) = F_1$
3. für alle und a ∈ A ist φ ( q ) ⋅ a = φ ( q ⋅ a ) .$q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

Man kann zeigen, dass diese Bedingungen implizieren, dass notwendigerweise surjektiv ist (und somit | Q 2 | ⩽ | Q 1 | ). Darüber hinaus gibt es höchstens einen Morphismus von A 1 bis A 2, und wenn dieser Morphismus existiert, erkennen A 1 und A 2 dieselbe Sprache. Nun kann man zeigen, dass es für jede Sprache L ein eindeutiges vollständig zugängliches DFA A L gibt , das L akzeptiert, und dass für jedes vollständig zugängliche DFA akzeptiert$\varphi$$|Q_2| \leqslant |Q_1|$${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$L A A L L A L A A$\cal A$$L$gibt es einen Morphismus von auf . Dieser Automat wird als minimaler DFA von . Beachten Sie wieder , dass , da die Anzahl der Zustände in kleiner ist als die Anzahl der Zustände in , ist auch minimal im ersten Sinne.$\cal A$${\cal A}_L$$L$${\cal A}_L$$\cal A$${\cal A}_L$

Erwähnenswert ist, dass es auch eine geeignete algebraische Definition für unvollständige DFAs gibt. Siehe [Eilenberg, Automata, Languages ​​and Machines , vol. A, Academic Press, 1974] für weitere Einzelheiten.

2. Zurück zu unendlichen Worten

Die Erweiterung der ersten Definition funktioniert nicht, wie Shaull in seiner Antwort gezeigt hat. Und leider kann man auch zeigen, dass sich die universelle Eigenschaft der zweiten Definition nicht auf unendliche Wörter erstreckt, außer in einigen besonderen Fällen.

Ist es das Ende der Geschichte? Warten Sie eine Sekunde, es gibt ein weiteres minimales Objekt, das reguläre Sprachen akzeptiert ...

3. Der syntaktische Ansatz

Kehren wir zunächst noch einmal zu endlichen Worten zurück. Recall , dass eine Sprache von wird von einem monoid erkannt , wenn es ein surjektiv monoid morphism und eine Untergruppe von , so dass . Auch hier gibt es ein monoid , die angerufene syntaktischen monoid von , das erkennt und ist ein Quotient aus allen Monoide Erkennen . Dieses syntaktische Monoid kann durch die syntaktische Kongruenz von direkt als Quotient von definiert werdenA * M f : A * → M P M F - 1 ( P ) = L M ( L ) L L L A * ~ L L U ~ L v ,  wenn und nur wenn für alle  x , y ∈ A * ,  x u y ∈ $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$$L$$L$$L$$A^*$ $\sim_L$$L$, definiert wie folgt: die gute Nachricht ist, dass Dieses Mal wurde dieser Ansatz auf unendliche Wörter erweitert, aber es dauerte lange, bis die entsprechenden Begriffe gefunden waren. Zunächst wurde der geeignete Begriff einer syntaktischen Kongruenz von A. Arnold gefunden (Eine syntaktische Kongruenz für rationale Sprachen, Theoret. Comput. Sci. 39 , 2-3 (1985), 333–335). Die Ausweitung syntaktischer Monoide auf die Einstellung unendlicher Wörter erforderte eine komplexere Art von Algebren, die heutzutage Wilke-Algebren zu Ehren von T. Wilke genannt werden, der sie als erster definierte (T. Wilke, Eine algebraische Theorie für reguläre Sprachen von endlich und unendlich Wörter,

4. Fazit

Es gibt also eine mathematisch fundierte Vorstellung von einem Minimalobjekt, das eine bestimmte reguläre akzeptiert , aber nicht auf Automaten beruht. Dies ist eigentlich eine eher allgemeine Tatsache: Automaten sind ein sehr leistungsfähiges algorithmisches Werkzeug, aber sie reichen nicht immer aus, um mathematische Fragen zu Sprachen zu behandeln.$\omega$