¿Caracterización de

16

Es una prueba estándar en cursos de autómatas que para y | Σ | 2 que S ( L ) = { w w : w L } no es un lenguaje sin contexto.L=Σ|Σ|2S(L)={ww:wL}

También es cierto que para cualquier finito , S ( L ) es finito (y, por lo tanto, un CFL). Supongo que L siendo infinito y regular no es "suficiente" para que S ( L ) no sea un CFL. Editar : ¿qué pasa con no CFL L ?LS(L)LS(L)L

¿Hay alguna caracterización de que tiene S ( L ) no siendo un CFL?LS(L)

Ryan
fuente
Si entiendo correctamente, la pregunta es decidir, dado un lenguaje regular , si S ( L ) está libre de contexto o no. LS(L)
J.-E.
2
1. ¿Puede contarnos más sobre qué tipo de caracterización está buscando? ¿Está buscando un algoritmo que, dado , decida si S ( L ) está libre de contexto? ¿Está buscando algunas condiciones en L que sean suficientes para garantizar que S ( L ) esté libre de contexto? ¿Qué forma le gustaría que tomara una caracterización? 2. Si no recibe ninguna respuesta después de unos días y prefiere ver esto en CSTheory.SE, no dude en marcarlo para la atención del moderador y solicitar que se migre. LS(L)LS(L)
DW
@DW 1. Cualquiera estaría bien, pero preferiría condiciones suficientes. 2. Gracias por el consejo!
Ryan
1
@Ryan solo condiciones suficientes? Bueno, aquí hay un par: (a) L es regular y para cada en L , w = w R (b) L es CF y para todo n , L Σ n está vacío o es igual a Σ n . Sin embargo, estos definitivamente no son necesarios. Si no obtiene respuestas aquí, mueva la pregunta a cstheory. ¡Tengo mucha curiosidad por las condiciones necesarias y suficientes! wLw=wRnLΣnΣn
aelguindy
infinito y regular no es suficiente para S ( L ) no CF. Si Σ = { a , b , c } , L = a entonces S ( L ) = ( a a ) que es regular, por lo tanto, CF. LS(L)Σ={a,b,c},L=aS(L)=(aa)
chi

Respuestas:

2

Más de un comentario extendido con una conjetura, pero aquí hay una condición que parece capturar el problema, en el contexto de regular para que S ( L ) esté libre de contexto.LS(L)

Condición En el mínimo DFA para L , cualquier ruta de aceptación contiene como máximo un bucle.AL

Excepción: se permiten dos bucles si sus etiquetas y la etiqueta del prefijo antes del primer bucle se conmutan, y el sufijo después del segundo bucle está vacío. Por ejemplo, está bien.aab(aa)

Recuerde que dos palabras y v conmutan si son potencias de una misma palabra t . Podemos suponer que el sufijo está vacío, porque no puede estar no vacío y conmutar con la etiqueta del segundo bucle en un DFA.uvt

Suficiente Asuma la condición, usted construye un PDA para tratando cada patrón de aceptación x u y de A donde u etiqueta un bucle simple. Queremos aceptar palabras de la forma x u n y x u n y . Leemos x , presionamos un símbolo para cada aparición de u , leemos y x , luego hacemos estallar un símbolo para cada aparición de u , y finalmente leemos y .LxuyAuxunyxunyxuyxuy

Sobre la excepción, si estamos en este caso, una ruta de aceptación básica es de la forma donde u , v son las etiquetas de los bucles. Aceptamos palabras de la forma x u n y v m x u n y v m , pero por suposición ( x , u , v conmutar) es lo mismo que u n x y u n v m x y v m , que puede ser hecho por un PDA: presione nxuyvu,vxunyvmxunyvmx,u,vunxyunvmxyvmnveces (para casos de ), lea x y , pop n veces, presione m veces (para v ), lea x y , pop m veces.uxynmvxym

El PDA final es la unión de los PDA para cada patrón.

Necesario (saludo manual) Si hay una ruta con dos bucles, incluso en el caso más simple en el que debe tomar uno y luego el otro (por ejemplo ), debe recordar cuántas veces se toma cada uno, pero la estructura de la pila evita que las repitas en el mismo orden. Tenga en cuenta que el hecho de que el DFA es mínimo es importante en la caracterización, para evitar el uso de dos bucles cuando uno podría ser suficiente.ab

Por ahora, la parte necesaria es solo una conjetura, y podrían necesitarse más excepciones para obtener la condición exacta. Me interesarían los contraejemplos.

Denis
fuente
"y luego leyendo w nuevamente, haciendo aparecer un símbolo para cada bucle tomado en la segunda aparición de la palabra" - ¡pero hay infinitamente tales ! A menos que esté leyendo tu argumento incorrectamente. w
Ryan
@Ryan el número de "patrones" xuy donde u etiqueta un bucle es finito, por lo que podemos adivinar cuál estamos leyendo.
Denis
Edité para aclarar esta parte.
Denis
La condición me parece similar a otra que tenía en mente: S (L) está libre de contexto si no existen las palabras , de modo que w 1 y w 2 no son prefijos el uno del otro y u ( w 1 + w 2 ) * v L . u,v,w1,w2w1w2u(w1+w2)vL
holf
@holf el tuyo no parece funcionar para ab
Denis