Prueba fácil de que los lenguajes sin contexto se cierren bajo un cambio cíclico

El desplazamiento cíclico (también llamado rotación o conjugación ) de un lenguaje se define como . Según Wikipedia (y aquí ), los lenguajes libres de contexto se cierran bajo esta operación, con referencias a documentos de Oshiba y de Maslov. ¿Hay una prueba fácil de este hecho?{ y x ∣ x y ∈ L $L$$\{ yx \mid xy \in L \}$

Para los idiomas regulares, el cierre se analiza en este formulario como " Probar que los idiomas regulares están cerrados bajo el operador de ciclo ".

Puede intentar usar autómatas pushdown. Dado un autómata pushdown para el idioma original, construimos uno para el cambio cíclico. El nuevo autómata opera en dos etapas, correspondientes a la parte y de la palabra (donde está en el idioma original). En la primera etapa, cuando el autómata le gustaría hacer estallar un no terminal , que puede empujar un lugar no terminal ; La idea es que al final de la primera etapa, la pila contendría, en orden inverso, los símbolos que se encuentran en la pila después de leer por el autómata original. En la segunda etapa (el interruptor es no determinista), en lugar de empujar un no-terminalx y x x y A A ′ x A A ′$y$$x$$yx$$xy$$A$$A'$$x$$A$, se nos permite reventar una no terminal . Si el autómata original puede generar la pila al leer , entonces la nueva podría reventar exactamente toda la pila.$A'$$x$

Editar: Aquí hay más detalles. Supongamos que tenemos un PDA con alfabeto , conjunto de estados , conjunto de estados de aceptación , no terminales , estado inicial y un conjunto de transiciones permitidas. Cada transición permitida es de la forma , lo que significa que cuando está en el estado , al leer (o , en cuyo caso es una transición libre), si la parte superior de la pila es (o , lo que significa que la pila está vacía), entonces el PDA puede (es un modelo no determinista) moverse al estado , reemplazandoQ F Γ q 0 ( q , a , A , q ′ , α ) q a ∈ A a = ϵ A ∈ Γ A = ϵ q ′ A α ∈ Γ $\Sigma$$Q$$F$$\Gamma$$q_0$$(q,a,A,q',\alpha)$$q$$a \in A$$a = \epsilon$$A \in \Gamma$$A = \epsilon$$q'$$A$ con .$\alpha \in \Gamma^*$

El nuevo PDA tiene una nueva no terminal para cada . Por cada dos estados y , hay dos estados . Los estados iniciales (el estado inicial real se elige de forma no determinista entre ellos mediante -transitions) son . Para cada transición hay transiciones correspondientes y . También hay otras transiciones.$A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$$(q,q,1)$$(q,a,A,q',\alpha)$$((q,q'',1),a,A,(q',q'',1),\alpha)$$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

Para cada transición , hay transiciones , donde y . Para cada estado final , hay transiciones , donde .$(q,a,A,q',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$$\epsilon' = \epsilon$$q \in F$$((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$$A \in \Gamma \cup \{\epsilon\}$

Para cada transición , hay transiciones , donde . Para cada transición , hay transiciones , donde . Para cada transición , hay "transiciones generalizadas" ; Estos se implementan como una secuencia de dos transiciones a través de un nuevo estado intermedio. Transiciones\ alpha) con$(q,a,\epsilon,q',\alpha)$$((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$$A \in \Gamma \cup \{\epsilon\}$$(q,a,\epsilon,q',A)$$((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$$B \in \Gamma \cup \{\epsilon\}$$(q,a,A,q',B)$$((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$$(q,a,\epsilon,q',\alpha)$$|\alpha| \geq 2$se manejan de manera similar. Para cada transición , hay transiciones , donde . Las transiciones se manejan de manera similar. Finalmente, hay un único estado final , y transiciones .$(q,a,A,q',A)$$((q,q'',2,A),a,B,(q',q'',2,A),B)$$B \in \Gamma' \cup \{\epsilon\}$$(q,a,A,q',A\alpha)$$f$$((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$

(Puede haber algunas transiciones que me perdí, y algunos de los detalles que estoy omitiendo son algo desordenados).

Recuerde que estamos tratando de aceptar una palabra , donde es aceptada por el PDA original. Un estado significa que estamos en la etapa 1, en el estado , y el PDA original está en el estado después de leer . Un estado es similar, donde corresponde a la última que apareció. En la etapa 1, se nos permite empujar en lugar de hacer estallar . Hacemos eso para cada no terminal que se produce al procesar , pero solo aparece al procesar . En la etapa 2, se nos permite reventar$yx$$xy$$(q,q',1)$$q$$q'$$x$$(q,q',2,A)$$A$$A'$$A'$$A$$x$$y$$A'$en lugar de empujar . Si hacemos esto, entonces debemos recordar que la parte superior del stock es realmente ; esto solo se aplica cuando no hay cosas "temporales" en la pila, que en el PDA simulado es lo mismo que la parte superior de la pila es o de la forma .$A$$A$$\epsilon$$B'$

Aquí hay un ejemplo simple. Considere un autómata para que empuja para cada , y saca para cada . El nuevo autómata acepta palabras de dos formas: y . Para las palabras de la primera forma, etapa 1 consiste en empujar veces'etapa 2 consiste en hacer estallar veces , empujando veces , y haciendo estallar veces . Para palabras de la segunda forma, primero presionamos veces$x^n y^n$$A$$x$$A$$y$$y^k x^n y^{n-k}$$x^k y^n x^{n-k}$$k$$A'$$k$$A'$$n-k$$A$$n-k$$A$$k$$A$, luego pop veces , push veces , transición a la etapa 2 y pop veces .$k$$A$$n-k$$A'$$n-k$$A'$

Aquí hay un ejemplo más complicado, para el lenguaje de paréntesis equilibrados de varios tipos ("()", "[]", "<>") de modo que los descendientes inmediatos de cada tipo de paréntesis deben pertenecer a un tipo diferente. Por ejemplo, "([] <>)" está bien pero "()" está mal. Para cada uno "(", empujamos si la pila top-of-no es , por cada ")", nos pop . De manera similar , , están asociados con "[]" y "<>". Así es como aceptamos la palabra ">) ([()] <". ">)", presionando , y transición a la etapa 2. "(", haciendo estallary recordando el tope de la pila . Consumimos "[()]", empujando y haciendo estallar ; al empujar$A$ $A$$A$$B$$C$$C'A'$$A'$$A$$BA$$B$ , somos conscientes de que la parte superior "real" de la pila es , por lo que se permiten corchetes (">) (() <") no nos engañaría; al presionar , ya que la parte superior de la pila es (que no es o de la forma ), entonces sabemos que también es la parte superior "real" de la pila, por lo que se permiten paréntesis redondos (aunque la parte superior de la pila de la sombra es ). Finalmente, consumimos "<" y aparece .$A$$A$$B$$\epsilon$$X'$$B$$A$$C'$

Considere la forma normal de Greibach . Para construir un lenguaje modificado solo necesita cambiar las producciones a y agregar una nueva no terminal que se comporte como solía, en caso de que algunos producción de referencia .$S \to \alpha A_1 \dots A_n$$S \to A_1\dots A_n \alpha$$S'$$S$$S$

Resultó ser una buena idea revisar el viejo clásico de Hopcroft y Ullman Introducción a la teoría de los autómatas (1979). El cierre bajo el ciclo es el ejercicio 6.4c y está marcado como S **. Las estrellas dobles significan que es uno de los problemas más difíciles (en el libro). Afortunadamente, la S indica que es uno de los problemas seleccionados con una solución.

La solución es la siguiente. Tome un CFG en forma normal de Chomsky. Considere cualquier árbol de derivación y básicamente déle la vuelta. Considere una ruta en el árbol original. A la izquierda, el árbol tiene contribuciones a la derecha , lo que significa que la cadena derivada es igual a . (En realidad, como la gramática es CNF cuando el camino continúa hacia la izquierda, la contribución será hacia la derecha y la correspondiente está vacía, etc.)$S=X_1, X_2, \dots , X_n$$x_1, x_2, \dots, x_n$$y_1, y_2, \dots, y_n$$x_1 x_2 \dots x_n y_n \dots y_2 y_1$$x_i$

El árbol al revés tiene una ruta con contribuciones a la izquierda y a la derecha, por lo que el resultado es una derivación para . Según sea necesario.$S', \hat X_n, \dots \hat X_2, \hat X_1$$y_n, \dots, y_2 y_1$$x_n, \dots, x_2 x_1$$y_n \dots y_2 y_1 x_1 x_2 \dots x_n$

Los detalles completos de la construcción se dan en el libro.

Observe cómo esto recuerda la solución (aceptada) de Yuval. Los no terminales que se empujan en lugar de explotar están en el orden opuesto en la pila. Muy similar a al revés en el árbol.