Cierre contra el cociente correcto con un lenguaje fijo

13

Realmente me encantaría tu ayuda con lo siguiente:

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

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

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

Las opciones relevantes son:

  1. Los idiomas regulares están cerrados bajo resp. A r , para cualquier idioma L 2AlArL2

  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 .L2AlArL2AlAr

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).wLw=xyxyyL2

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

Jozef
fuente
¿Qué es la ? ¿Quiere decir ' no están cerrados' en la segunda parte de (b)? ¿Qué es la L ? AL
Alex ten Brink
¿Todavía no has definido ? L
Gopi
@Gopi es un lenguaje de entrada. A ( ) es un operador de idiomas en ambos casos. LA()
Lucas Cook,
@Gopi: es un parámetro de A , L 2 es fijo. LAL2
Raphael
Oups mi mal, ¿cómo no vi esto oO.
Gopi

Respuestas:

11

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


Comencemos por la pregunta fácil: (pregunta parte 2). Tome L 2 como indecidible y L = { ε } . ¿Lo que pasa?Al(L)L2L={ε}

(moral: siempre verifique los "extremos": vacío , L = { ε } y L = Σ ...)LL={ε}L=Σ


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?ArArL2L2

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

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.L2A(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 LLDFALxqyL2qyDFALyL2qDFAALsi 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 .yL2qyDFAL

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 .DFAALDFALqyL2yqDFAL

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.L2L2

Sonó.
fuente
Parece que publicó una respuesta al problema en sí al mismo tiempo. :]
Lucas Cook
well.. my answer has spoilers in it.. maybe I should put a spoiler alert, so one can start with your answer and if this is not enough - then get the details..
Ran G.
Wow, wonderful answer, very helpful. Thanks a lot Ran!
Jozef
7

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 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.
  • If you think that you cannot, you would typically find example languages L and L2 such that Ax 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 Al(L)=L2/L while Ar(L)=L/L2, where 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
fuente