Abschluss gegen rechten Quotienten mit einer festen Sprache

13

Ich würde mich sehr über Ihre Hilfe bei Folgendem freuen:

Für jedes feste L2 ich entscheiden, ob es einen Abschluss unter den folgenden Operatoren gibt:

  1. Ar(L)={xyL2:xyL}

  2. .Al(L)={xyL:xyL2}

Die relevanten Optionen sind:

  1. Reguläre Sprachen sind unter bzw. geschlossen. A r , für jede Sprache L 2AlArL2

  2. Für einige Sprachen sind reguläre Sprachen unter A l bzw. L 2 geschlossen . A r und für einige Sprachen L 2 sind reguläre Sprachen nicht unter A l bzw. L 2 geschlossen . A r .L2AlArL2AlAr

Ich habe geglaubt, dass die Antwort für (1) (2) sein sollte, denn wenn ich ein Wort in und w = x y bekomme , kann ich einen Automaten bauen, der erraten kann, wo x zu y wird , aber dann muss er sich verifizieren dass y zu L 2 gehört und wenn es nicht regelmäßig ist, wie würde es das tun? Die Antwort dafür ist (1).wLw=xyxyyL2

Was kann ich tun, um diese Operatoren korrekt zu analysieren und festzustellen, ob die regulären Sprachen darunter geschlossen sind oder nicht?

Jozef
quelle
Was ist ? Meinen Sie im zweiten Teil von (b) "sind nicht geschlossen"? Was ist L ? AL
Alex ten Brink
Sie haben noch nicht definiert, ? L
Gopi
@Gopi ist eine Eingabesprache. Ein ( ) ist in beiden Fällen ein Operator für Sprachen. LA()
Lucas Cook
@Gopi: ist ein Parameter von A , L 2 ist fest. LAL2
Raphael
Oups my bad, wie habe ich das nicht gesehen oO.
Gopi

Antworten:

11

Um diese Frage zu beantworten, müssen wir zulassen , dass jeder . Nehmen wir also an, dass L 2 eine sehr komplexe Sprache ist (sagen wir eine unentscheidbare Sprache).L2L2


Beginnen wir mit der einfachen Frage: (Frage Teil 2). Nimm L 2 als unentscheidbar und L = { ε } . Was geschieht?Al(L)L2L={ε}

(moral: Überprüfen Sie immer die "Extreme": leer , L = { ε } und L = Σ * ...)LL={ε}L=Σ


Nun zu . Dies ist eine großartige Frage (normalerweise eine Bonusfrage in Final / Homeworks). In der Tat sind reguläre Sprachen unter A r für jede Sprache L 2 geschlossen . Auch unentscheidbar L 2 . Cool, richtig?ArArL2L2

Wie können wir also einen Automaten für wenn es keine Maschine gibt, die L 2 akzeptiert ?Ar(L)L2

Hier kommt die Magie des "abstrakten Denkens", dh des existenziellen Beweises . Wenn jemand uns gibt können wir diese Informationen benutzen , um zu zeigen , dass es existiert eine gewissen Automaten zu lösen A ( L ) . Nun die Details.L2A(L)

Wir gehen vom Automaten von (Aufruf ist D F A L ). Nehmen wir an, dass wir nach der Verarbeitung von x in einem Zustand q enden . Wir müssen akzeptieren , wenn es existiert , y L 2 derart , dass , wenn wir von weiterhin q Verarbeitung y wir in einem Endzustand werden am Ende D F A L . Es gibt keine Maschine, die uns sagen kann, ob y in L 2 ist , aber wir können q zu einem Endzustand von D F A A L machenLDFALxqyL2qyDFALyL2qDFAALWenn die obige Bedingung zutrifft, dh wenn es etwas so dass, wenn wir bei q beginnen und y verarbeiten, wir in einem Endzustand von D F A L enden .yL2qyDFAL

so bauen wir untersuchen jeden der Zustände von D F A L und machen jeden Zustand q eine akzeptierende Zustand , wenn wir etwas nehmen kann y L 2 und das y wird uns aus führen q zu einem akzeptierenden Zustand D F A L .DFAALDFALqyL2yqDFAL

Also ok, ist unendlich, und wir haben vielleicht keinen Computer, um alle Wörter in L 2 aufzulisten , aber das ist alles egal ... der obige Automat ist gut definiert, auch wenn ich ihn nicht zeichnen kann zu Ihnen Staat für Staat. Magie.L2L2

Ran G.
quelle
Sieht so aus, als hätten Sie gleichzeitig eine Antwort auf das Problem selbst veröffentlicht. :]
Lucas Cook
naja .. meine antwort hat spoiler drin .. vielleicht sollte ich einen spoiler alarm setzen, damit man mit deiner antwort anfangen kann und wenn das nicht reicht - dann hol die details ..
ran g.
Wow, wundervolle Antwort, sehr hilfreich. Vielen Dank Ran!
Jozef
7

Ich bin mir nicht sicher, ob Sie nach einer Antwort auf das Problem suchen oder nicht, daher gebe ich sie nicht direkt weiter. (Ich kann, wenn du es willst.)

Du hast gefragt:

Was kann ich tun, um diese Operatoren korrekt zu analysieren und festzustellen, ob die regulären Sprachen darunter geschlossen sind oder nicht?

Ihr Ansatz ist gut. Wie bei allen "offenen" theoretischen Fragen sollten Sie ein intuitives Gefühl dafür bekommen, ob es wahr ist oder nicht. In der Regel werden hierfür Beispiele ausprobiert (sowohl Common- als auch Edge-Case-Beispiele) oder Sonderfälle untersucht (z. B. Was wäre, wenn?)L2 is regular? context-free?). For this problem, you need to develop some guess as to whether you can build an automaton/regex for the operators or not. After that:

  • If you think that you can, you need to be able to construct this automaton/regex for any regular input language L.
  • Wenn Sie glauben, dass dies nicht möglich ist, finden Sie normalerweise Beispielsprachen L und L2 so dass Ax ist nicht geschlossen.

(Und wenn ein Ansatz nicht funktioniert, können Sie immer den anderen versuchen.)


Für das Problem selbst:

Diese beiden sind die richtigen Quotientenoperatoren. (Ich glaube, der linke Quotient besteht darin, das Postfix anstelle des Präfix zu belassen.) Der Unterschied zwischen den beiden besteht darin, dassEINl(L)=L2/L während EINr(L)=L/L2, wo L2 is fixed in both cases.

You have some intuition about Ar, so here's something to think about for Al: Al gives a modified version of L2. Since L2 could be nonregular, is it possible for Al to leave L2 unchanged? If so, then Al is not regular in that case. Otherwise, we will have to argue that Al makes L2 regular in all cases.

Lucas Cook
quelle