Cierre contra el cociente correcto con un lenguaje fijo

Realmente me encantaría tu ayuda con lo siguiente:

Para cualquier fijo $L_2$, necesito decidir si hay un cierre bajo los siguientes operadores:

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\}$ .

Las opciones relevantes son:

1. Los idiomas regulares están cerrados bajo resp. A r , para cualquier idioma L $A_l$$A_r$$L_2$

2. Para algunos idiomas , los idiomas regulares están cerrados bajo A l resp. A r , y para algunos idiomas L 2 , los idiomas regulares no están cerrados bajo A l resp. A r .$L_2$$A_l$$A_r$$L_2$$A_l$$A_r$

Yo creía que la respuesta para (1) debe ser (2), porque cuando llego a una palabra en y W = x y puedo construir un autómata que se puede adivinar dónde x girando a Y , pero entonces tiene que verificar que y pertenece a L 2 y si no será regular, ¿cómo lo haría? La respuesta para eso es (1).$w \in L$$w=xy$$x$$y$$y$$L_2$

¿Qué debo hacer para analizar esos operadores correctamente y determinar si los idiomas normales están cerrados debajo de ellos o no?

Para responder a esta pregunta, necesitamos permitir cualquier . Entonces, pensemos que L 2 es un lenguaje muy complejo (digamos, un lenguaje indecidible).$L_2$$L_2$

Comencemos por la pregunta fácil: (pregunta parte 2). Tome L 2 como indecidible y L = { ε } . ¿Lo que pasa?$A_l(L)$$L_2$$L=\{\varepsilon\}$

(moral: siempre verifique los "extremos": vacío , L = { ε } y L = Σ ∗ ...)$L$$L=\{\varepsilon\}$$L=\Sigma^*$

Ahora para . Esta es una gran pregunta (generalmente una pregunta adicional en Final / Homeworks). De hecho, los idiomas regulares están cerrados bajo A r para cualquier idioma L 2 . Incluso indecidible L 2 . ¿Guay, verdad?$A_r$$A_r$$L_2$$L_2$

Entonces, ¿cómo podemos construir un autómata para si no hay una máquina que acepte L 2 ?$A_r(L)$$L_2$

Aquí viene la magia del "pensamiento abstracto", es decir, la prueba existencial . Si alguien nos da , podemos usar esta información para mostrar que existe algún autómata para resolver A ( L ) . Ahora los detalles.$L_2$$A(L)$

Partimos del autómata de (la llamada es D F A L ). Suponga que después de procesar x terminamos en un estado q . Tenemos que aceptar si existe y ∈ L 2 de tal manera que si continuamos de q procesamiento y vamos a terminar en un estado final de D M A L . No hay una máquina que pueda decirnos si y está en L 2 , pero podemos hacer q un estado final de D F A A $L$$DFA_L$$x$$q$$y\in L_2$$q$$y$$DFA_L$$y$$L_2$$q$$DFA_{A_L}$si la condición anterior se mantiene, es decir, si existe algún de tal manera que si comenzamos a q y proceso y terminamos en un estado final de D F A L .$y\in L_2$$q$$y$$DFA_L$

así que para construir examinamos cada uno de los estados de D F A L y hacemos de cada estado q un estado de aceptación si podemos tomar algunos y ∈ L 2 y este y nos llevará de q a un estado de aceptación de D F A L .$DFA_{A_L}$$DFA_L$$q$$y\in L_2$$y$$q$$DFA_L$

Bien, es infinito, y es posible que no tengamos una computadora para enumerar todas las palabras en L 2 , pero todo esto no importa ... el autómata anterior está bien definido, incluso si no puedo dibujarlo a ti estado por estado. Magia.$L_2$$L_2$

I'm not sure if you are looking for an answer to the problem or not, so I don't provide it directly. (I can if you want it, though.)

You asked:

What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?

Your starting approach is a good one. As with all "open" theory questions, you should get an intuitive feel for whether it is true or not. Usually this is by trying examples (both common and edge-case) or investigating special cases (e.g. what if $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$.
• If you think that you cannot, you would typically find example languages $L$ and $L_2$ such that $A_x$ is not closed.

(and if one approach isn't working, you can always try the other.)

For the problem itself:

These both are the right quotient operator. (I believe left quotient involves leaving the postfix instead of the prefix.) The difference between the two is that $A_l(L) = L_2 / L$ while $A_r(L) = L / L_2$, where $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.