Myhill-Nerode und Verschlusseigenschaften

8

Es ist bekannt, dass reguläre Sprachen durch die Myhill-Nerode-Äquivalenz gekennzeichnet sind. Für die Sprache über definieren die Äquivalenz über iff für alle Wir haben . Dann ist regulär, wenn endlichen Index hat, dh eine endliche Anzahl von Äquivalenzklassen hat.LΣxLyΣzΣxzLyzLLL

Ich weiß, dass die Beziehung verwendet werden kann, um zu zeigen, dass einige Sprachen nicht regulär sind, indem unendlich viele Zeichenfolgen angegeben werden, die nicht äquivalent sind.

Meine Frage: Können wir Myhill-Nerode problemlos verwenden, um die Schließungseigenschaften regulärer Sprachen anzuzeigen? Oder sollten wir die "syntaktische Kongruenz" von Sprachen verwenden?

Als Beispiel für ein Präfix ist es einfach, da impliziert . Aber wie gehen wir mit Suffix, Verkettung, Stern, Spiegel um?xLyxpref(L)y

Hendrik Jan.
quelle

Antworten:

6

Ich schließe unter booleschen Operationen mit der MyHill-Nerode-Charakterisierung. Ich habe es noch nie so gesehen. Eine rechte Kongruenz sättigt eine Sprache wenn oder äquivalent, wenn eine Vereinigung von Kongruenzklassen ist. Wir gebrauchen:L

uv(uLvL)
L

Satz: (MyHill-Nerode) Eine Sprache ist genau dann regulär, wenn es eine Rechtskongruenz des endlichen Index gibt, die sättigt .L

Nehmen wir nun an, wir haben reguläre Sprachen und bezeichnen einige richtige Kongruenzen des endlichen Index, die sie sättigen. Dann ist eine rechte Kongruenz (der Schnittpunkt von beiden) und verfeinert beide. Außerdem haben wir Wir haben also eine endliche Anzahl von Äquivalenzklassen. Dies ergibt auch, dass der Schnittpunkt der Äquivalenzklassen und entweder leer ist oder ein gemeinsames Element und daher der ÄquivalenzklasseL1,L2XL1,L2

uv:⇔uL1vuL2v
[u]=[u]L1[u]L2.
[u]L1[v]L2w[w]. Dies ergibt, dass entweder leer ist oder als Vereinigung der Äquivalenzklasse für . Nach dem obigen Satz ist regulär.L1L2L1L2

Für es eine Vereinigung von Äquivalenzklassen für und , die selbst Vereinigungen von Äquivalenzklassen für , daher ist es auch regulär. Und zur Ergänzung folgt dies als die Äquivalenzklassenpartition , daher eine richtige Kongruenz, die für funktioniertL1L212XL1 funktioniert auch für XL1.

Zusätzliche Kommentare: In Ihrer Frage haben Sie auch die kanonische Nerode-Rechtskongruenz erwähnt

uLv:⇔(wX:uwLvwL)
mit LX. Dies ist die gröbste Sättigung der rechten KongruenzL. Nun könnte es natürlich sein zu fragen, ob wir die richtige Nerode-Kongruenz von konstruieren könnenL1L2 oder L1L2 leicht aus denen für L1,L2oder wenn die resultierende Schnittpunktkongruenz als eine richtige Nerode-Kongruenz auftritt. Vielleicht finden wir so einfache Formeln wie
uL1L2vuL1vuL2v.
Aber das oben Genannte gilt nicht. Und meines Wissens gibt es keine einfache Beziehung. Zum Beispiel überlegenL1=(aa) und L2=a(aa)+, dann haben wir
L1L2=,L1L2=X{a}.
Jetzt L1L2 hat mindestens vier Kongruenzklassen, wie es verfeinert L2Das hat genau vier Kongruenzklassen. Aber hat genau eine Klasse und X{a} hat drei (könnte alle leicht mit minimalen vollständigen Automaten gesehen werden).

EDIT (2019.08.18). Die Spiegel- und Suffixoperation beziehen sich auf die linke Kongruenz

uLvwX:wuLwvL.
Wenn L hat einen endlichen Index, ähnlich wie für die Präfixoperation und die Rechtskongruenz, suffix(L)hat endlichen Index. Und uLv iff mirror(u)mirror(L)mirror(v);; und da ist die Spiegeloperation eine Bijektion aufX die letzte Gleichung gibt das mirror(L) hat endlichen Index iff L hat einen endlichen Index (beachten Sie, dass die linke Kongruenz den gleichen Index hat wie die rechte Kongruenz für die gespiegelten Wörter, aber im Allgemeinen eine rechte Kongruenz für mirror(L) könnte exponentiell viel mehr Klassen haben, wie durch Standardkonstruktionen aus der Automatentheorie gezeigt wird).

Diese Operationen werden also behandelt, wenn wir zeigen können, dass beide Kongruenzen gleichzeitig einen endlichen Index haben oder nicht. Schauen wir uns dazu die syntaktische Kongruenz an

uS(L)vx,yX:xuyLxvyL.
Diese Kongruenz verfeinert beide obigen Kongruenzen. Wenn sie also endlich ist, sind auch beide obigen Kongruenzen endlich. Es istuS(L)v iff für alle wX wir haben [wu]L=[wv]LDaher haben wir eine gut definierte und injektive Karte aus dem S(L)-Äquivalenzklassen zu den Transformationen auf {[w]L:wX}und wenn letzteres eine endliche Menge ist, ist auch die Menge dieser Transformationen endlich, was dies impliziert S(L)ist von endlichem Index. Insgesamt haben wir das alsoL hat endlichen Index wenn L hat endlichen Index, das Gegenteil ist ähnlich impliziert.

StefanH
quelle
4

Die Äquivalenzklassen der Myhill-Nerode-Beziehung sind auch die Zustände des minimalen DFA für die Sprache. Was auch immer mit DFAs einfach zu zeigen ist, Sie können es in einen Proof konvertieren, der den Myhill-Nerode-Standpunkt verwendet. Wo immer Sie NFAs benötigen, können Sie erwarten, dass der Beweis komplizierter wird.

Aber die richtige Antwort lautet: Probieren Sie es selbst aus! So wird geforscht.

Yuval Filmus
quelle
Nun, ich habe nicht um originelle Forschung gebeten, danke. Ich hatte gehofft, dass jemand wusste, ob das Wissen vonK ein endlicher Index zu sein würde vorhersagen ϕ(K) als endlicher Index, wo ϕist eine Sprachoperation. Ich habe es versuchtϕ= Präfix, aber ich kann nicht sehen, wie die Verkettung auf elegante Weise behandelt wird. Ja, ich kann ein anständiges DFA dafür erstellen.
Hendrik
Sicherlich können Sie leicht zwischen Nerode-Klassen und minimalen Automaten übersetzen, aber trotzdem habe ich einen Beweis hinzugefügt, der die Klassen verwendet, und meines Wissens konnte er nicht so einfach auf eine Automatenkonstruktion übertragen werden, da er mit den Klassen als Mengen funktioniert, was irgendwie ist vernachlässigt, wenn wir einen Automaten verwenden und beispielsweise einen Produktautomaten konstruieren, um Verschlusseigenschaften abzuleiten. Daher würde ich es als ein "wirklich" Argument betrachten, das nur für Nerode-Klassen gilt.
StefanH