Abschluss gegen rechten Quotienten mit einer festen Sprache

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

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

1. $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$

2. .$A_l(L)=\{x \mid \exists y \in L : xy \in L_2\}$

Die relevanten Optionen sind:

1. Reguläre Sprachen sind unter bzw. geschlossen. A r , für jede Sprache L $A_l$$A_r$$L_2$

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 .$L_2$$A_l$$A_r$$L_2$$A_l$$A_r$

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).$w \in L$$w=xy$$x$$y$$y$$L_2$

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

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).$L_2$$L_2$

Beginnen wir mit der einfachen Frage: (Frage Teil 2). Nimm L 2 als unentscheidbar und L = { ε } . Was geschieht?$A_l(L)$$L_2$$L=\{\varepsilon\}$

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

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?$A_r$$A_r$$L_2$$L_2$

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

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.$L_2$$A(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$$DFA_L$$x$$q$$y\in L_2$$q$$y$$DFA_L$$y$$L_2$$q$$DFA_{A_L}$Wenn 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 .$y\in L_2$$q$$y$$DFA_L$

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 .$DFA_{A_L}$$DFA_L$$q$$y\in L_2$$y$$q$$DFA_L$

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.$L_2$$L_2$

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?)$L_2$ 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 $L_2$ so dass $A_x$ 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, dass$A_l(L) = L_2 / L$ während $A_r(L) = L / L_2$, wo $L_2$ is fixed in both cases.

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