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.
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 ?
¿Hay alguna caracterización de que tiene S ( L ) no siendo un CFL?
context-free
Ryan
fuente
fuente
Respuestas:
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.L S(L)
Condición En el mínimo DFA para L , cualquier ruta de aceptación contiene como máximo un bucle.A L
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.aa∗b(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.u v t
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 .L xuy A u xunyxuny x u yx u y
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 nxuyv u,v xunyvmxunyvm x,u,v unxyunvmxyvm n veces (para casos de ), lea x y , pop n veces, presione m veces (para v ), lea x y , pop m veces.u xy n m v xy m
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.a∗b∗
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.
fuente